완주하지 못한 선수

Posted on Edited on In , ,

문제정의

두 배열이 주어진다. 한 배열은 참가자 명단(동명이인이 존재할 수도 있다.) 한 배열은 완주한 사람의 명단이 주어진다. 물론 순서는 뒤죽박죽인 것 같고 이 두 배열을 비교하여 완주하지 못한 한 명의 선수를 출력하면 된다.

문제풀이

문제 유형에는 해시라고 적혀있지만 해시가 익숙하지 않아 정렬을 이용하여 풀었다. 아래에 해시에 대한 얘기를 조금 써놓을 테니 이 풀이말고 해시를 이용해 풀고 싶은 분들은 참고하면 좋겠다.

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;

public class NotCompletePlayer {

    public static void main(String[] args)
    {
        String[] participant = {"leo", "kiki", "eden"};
        String[] completion = {"eden", "kiki"};

        String answer = "";
        PriorityQueue<String> pq = new PriorityQueue<>();
        PriorityQueue<String> comp = new PriorityQueue<>();
        for(int i = 0; i < participant.length; i++)
        {
            pq.add(participant[i]);
        }
        for(int i = 0; i < completion.length; i++)
        {
            comp.add(completion[i]);
        }
        
        for(int i = 0; i < completion.length; i++)
        {
            String name1 = pq.poll();
            String name2 = comp.poll();
            if(!name1.equals(name2))
            {
                answer = name1;
                break;
            }
        }
        if(answer.equals(""))
            answer = pq.poll();

        System.out.println(answer);
    }
    
}

부분부분 살펴보자

1
2
PriorityQueue<String> pq = new PriorityQueue<>();
PriorityQueue<String> comp = new PriorityQueue<>();

자바에서 기본적으로 정렬함수를 제시하지만 필자는 우선순위 큐를 활용하였다. 이건 각자의 취향인듯하니 넘기자. 이렇게 선언하면 알파벳이 낮은 순서(오름차순)로 정렬된다.

1
2
3
4
5
6
7
8
for(int i = 0; i < participant.length; i++)
{
    pq.add(participant[i]);
}
for(int i = 0; i < completion.length; i++)
{
    comp.add(completion[i]);
}

이제 참가자와 완주자명단을 우선순위 큐에 차례대로 집어넣는다. 우선순위큐에 넣는 것은 \(O(logn)\)만큼 걸린다. 따라서 participant의 길이를 n이라고 하면 시간복잡도는 \(O(nlogn)\)이다.

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 0; i < completion.length; i++)
{
    String name1 = pq.poll();
    String name2 = comp.poll();
    if(!name1.equals(name2))
    {
        answer = name1;
        break;
    }
}
if(answer.equals(""))
    answer = pq.poll();

둘 다 정렬되어 있는 상태라면 완주하지 못한 선수가 끼어있는 부분부터 이름이 다를 것이다는 것을 이용하였다. 큐에서 이름을 하나하나 빼면서 처음으로 이름이 안맞는 부분이 있으면 정답에 참가자 이름을 넣고 반복문을 탈출하도록 한다. 하지만 이러한 케이스는 어떨까?

participation : [aaa, bbb, ccc]

completion : [aaa, bbb]

이 경우 반복을 마쳐도 answer에 아무것도 들어가지 않는다. completion의 길이만큼 반복이 진행됨을 눈여겨 보자. 이 경우를 고려하여 if문이 들어간다. 이렇게 되면 ccc도 완주하지 못한 선수로 골라낼 수 있다.

시간복잡도는 \(O(nlogn)\)이며, 최종 시간복잡도 역시 같다.

테스트



해시

문제의 유형이 해시로 나타나 있는데 hashmap를 이용할 경우 \(O(n)\)으로 문제를 풀 수 있다. hashmap에 선수의 이름을 key값으로 하고 value를 1로 하여 넣는다. 만약에 동명이인이 있는 선수라면 getOrDefault를 이용하여 2,3,4...이런식으로 value를 업데이트한다. 참가자 명단에 대해 위 과정을 수행하면 다음엔 완주자 명단에 있는 사람들의 이름을 key값으로 (value-1)값을 다시 hashmap에 넣는다. 이렇게 되면 value가 1인 사람은 한명이 남는다. 완주하지 못한 선수를 찾기 위해 hashmap의 keySet을 이용하여 value가 1인 선수를 answer에 담으면 된다.