[프로그래머스] 완주하지 못한 선수

1. 문제

---

프로그래머스

2. 풀이 과정

---

이 문제를 가장 쉽게 푸는 방법은 하나하나 대조해가며 푸는 것이다.

 

모든 i에 대해 participant[i]와 같은 completion이 있는지를 찾고 그 completion을 지운다.

이렇게 되면 최종적으로는 participant에는 한명이 남게 되는데 이 사람이 답이 된다.

이 경우 시간복잡도는 O(N^2)이 나올 것이다.

그러나 이 문제의 입력 최대 크기가 10만이다. 즉, O(N^2)로는 풀 수 없다.

 

따라서 각 participant에 대해 completion을 조회하는 과정의 시간복잡도를 줄여야 한다. 

조회하는 과정을 효율적일 수 있게 하는 자료구조인 해시를 사용해야 한다.

 

그렇다면 HashMap, HashSet중에는 뭘 사용하는 것이 좋을까?

언뜻보면 이름 하나 있으니 HashSet 을 사용하면 될 것 같다. 하지만 HashSet 을 사용하면 안된다.

이 문제에는 동명이인이 가능하다는 조건이 있다. 바로 이 조건이 있기 때문에 HashSet을 사용할 수 없다.

 

participant가 ["james", "james", "tony"]이고  completion["james", "james"]인 경우를 생각해보자

 

1. completion을 HashSet에 저장한다.

이렇게 되면 HashSet은 중복을 허용하지 않으므로 ["james"]가 된다.

 

2. particpant가 HashSet에 있다면 HashSet에서 해당 데이터를 지운다.

1) paritipant[0]: "james"

HashSet에 있으므로 데이터를 지운다.

 --> HashSet: [ ]

 

2) participant[1]: "james"

HashSet에 없다. 

 

바로 이 부분이 문제가 된다. 

분명 completion에는 james가 두 명이 있지만 hashset에 저장했기 때문에 한명만 저장한 것처럼 처리된다.

따라서 답을 정상적으로 찾을 수가 없다.

 

따라서 이 문제에선 HashMap을 사용해야 한다.

Key값은 이름으로 하고 Value는 해당 Key가 등장한 횟수를 저장하면 된다.

그런 다음 participant와 같은 key가 존재하면 그 key의 value값을 하나 줄여주면 된다.

 

이런식으로 이 문제를 해결할 수 있다.

 

3. 내 코드

---

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        String answer = "";

        for(String name: completion) {
            if(map.containsKey(name)) {
                map.put(name, map.get(name) + 1);
            } else {
                map.put(name, 1);
            }
        }

        for(String name: participant) {
            if(map.containsKey(name)) {
                if(map.get(name) == 1) {
                    map.remove(name);
                } else{
                    map.put(name, map.get(name) - 1);
                }
            } else {
                answer = name;
            }
        }

        return answer;
    }
}

시간 복잡도

• O(N)

4. 피드백

---

• 조회를 효율적으로 할 수 있는 것은 Hash --> key로 데이터를 조회하기 때문
• Hash의 key는 중복을 허용하지 않는다.