문제

• N이 1명 이상 100,000명 이하이기 때문에 시간복잡도는 O(N log N)이나 O(N) 안에 풀어야 한다고 생각했다.

문제 풀이

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // 0. HashMap에 participant 저장
        // -> 중복이 존재하면 count ++ 해준다.
        HashMap<String, Integer> map = new HashMap<>();
        for(String s: participant){
            if(!map.containsKey(s)){ // map에 저장되지 않았다면
                   map.put(s, 1);
            }
            else{ // 이미 map에 저장되었다면
                map.put(s, map.get(s) + 1);
            }
        }
        
        // 1. completion를 돌면서, map에 존재하는지 확인
        // 1-1. map에 존재하고 value가 1이면 삭제, 존재하지 않는다면 return
        // 1-2. map에 존재하지만 value가 2 이상이라면 -1 해주기
        for(String cp: completion){
            if(!map.containsKey(cp)){
                return cp;
            }
            else{ // map에 존재하는 경우
                if(map.get(cp) >=2){
                    map.put(cp, map.get(cp)-1);
                }
                else{
                    map.remove(cp);
                }
            }
        }
        
        String result = "";
        // 2. 이름이 중복되는 경우에는 다 돌고 map에 남은 하나의 key값 return
        for(String key: map.keySet()){
            result = key;
        }
        return result;
    }
}

저번 특강 때, 강연자님이 코테에서 중요한 것은 "푸는 것!"이라고 하셨다. 코드가 한 두줄 늘어나는 거나, 변수 여러 개 선언하는 것들을 두려워하지 말라고 하셨다. 또, 시간 복잡도도 중요하긴 하지만 진짜 미세한 차이가지고 너무 신경쓰지 말라고 하셨다. 이 말씀이 너무 공감가면서 도움이 됐던 게 다 내가 하고 있던 행동이었기 때문이다.

뭔가 다른 사람의 풀이를 보면 코드도 짧고 간결하게 잘 짜셔서 나도 이렇게 짜야지! Stream이나 쓸 수 있는 라이브러리 있으면 써서 최대한 간결하게 짜려고 했던 버릇을 고쳐야 겠다고 생각했다.

그래서 이번 문제는 주석을 쓰면서, 쭉쭉 생각한 대로 풀었더니 코드는 길어졌지만 최대한 효율적인 것만 찾을 때보다 한결 문제를 풀기 편했다.

다른 사람의 풀이

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

• getOrDefault()
  • 나는 !map.containsKey(s)를 통해서 중복 체크를 했는데 굳이 if문을 사용하지 않아도 getOrDefault()로 간단하게 구현할 수 있다는 걸 새롭게 알았다.

시간 제한과 시간복잡도

제한 시간이 1초인 경우

• N = 500 => O(N^3)
• N = 2000 => O(N^2)
• N = 100,000 => O(N logN)
• N = 10,000,000 => O(N)

[참고]
https://zoosso.tistory.com/883
https://jeleedev.tistory.com/70
https://allo-ew.tistory.com/69