[Algo Rhythm🕺💃] 프로그래머스 고득점 Kit 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

나는 어떻게 풀었나

import java.util.HashMap;
import java.util.Iterator;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer;
        HashMap<String, Integer> runners = new HashMap<String, Integer>();
        
        for(String name : participant) {
            if(runners.containsKey(name)) {
                int num = runners.get(name) + 1;
                runners.replace(name, num);
            } else {
                runners.put(name, 1);
            }
        }
        
        for(String name : completion) {
            int num = runners.get(name);
            
            if(num > 1) { runners.replace(name, num - 1);}
            if(num == 1) { runners.remove(name); }
        }
        
        answer = runners.keySet()
                        .iterator()
                        .next();
        
        return answer;
    }
}

나는 왜 저렇게 풀었나

처음에는 직관적으로 brute force방식을 생각했다. 하지만 마라톤 경기를 참여한 선수의 수가 1명 이상 100,000명 이하이기 때문에 time complexity가 O(n^2)인 brute force는 적합하지 않다고 생각했다. 문제유형이 해시이기도 해고 그래서 해시맵을 사용하기로 했다.

 

처음에는 아래와 같은 알고리즘을 생각했다.

1. Participant 배열의 값을 key로 하고 index값을 value로 해서 해시맵에 저장한다.

2. 해시맵이 Completion 배열의 값을 key로 가지고 있는지 확인하고 가지고 있으면 해당 값을 삭제한다.

3. 해시맵에서 남아있는 이름을 확인한 후 return 한다.

하지만 이 알고리즘은 참가자 중 동명이인이 있는 경우에는 적용되지 않았다. 이름을 key값을 할 경우 이 이름을 가진 사람이 여러 명 있다는 것을 나타낼 수 있는 무언가가 필요했다. 생각해보니 처음 생각한 알고리즘에서는 value가 아무 의미없이 그냥 놀고 있었다. 그래서 value값으로 이 이름을 가진 사람의 수를 나타내기로 했다. 그렇게 아래와 같은 알고리즘이 탄생했다.

 

1. Participant 배열의 값(=참가자 이름)을 key로 하고 그 이름을 가진 사람의 수를 value로 해서 해시맵에 저장한다.

2. 해시맵이 completion 배열의 값(=완주자 이름)을 key값으로 가지는 경우 아래와 같이 동작한다.

   1. 그 이름을 가지고 있는 사람의 수가 1이면 해당 Key값을 삭제한다.

   2. 그 이름을 가지공 있는 사람의 수가 1보다 크면 value값을 decrement하여 replace한다.

3. 해시맵을 traverse해서 완주하지 못한 선수를 return한다.

나는 무엇을 배웠나

이름을 가진 사람의 개수를 나타내는 무언가가 필요하다는 것을 생각하기까지 시간이 꽤 걸렸다.

이 문제를 풀면서 내 알고리즘의 한계를 빠르게 파악할 수 있는 능력을 길러야겠다는 생각했다.