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

Benjamin·2023년 9월 24일

목록 보기

57/58

Troubleshooting 1

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<Integer, String> partici = new HashMap<>();
        
        for(int i =0; i<participant.length; i++) {
            partici.put(i,participant[i]);
        }
        
        for(int i=0; i<completion.length; i++) {
            partici.values().remove(completion[i]);
        }
        System.out.println(partici.size()); // 디버깅 출력
        answer = partici.get(0);
        return answer;
    }
}

문제

partici.get(0);이 undefined로 나올때도 있는데, 해시 사이즈를 보니 1이긴하네?

원인

아 get()은 Key값으로 찾는거구나..
나는 인덱스를 넣고있었다.

해결

values()로 value만 뽑아서, Iterator를 사용했다.
원소는 무조건 하나밖에 없을것이므로, 바로 next()한 값을 answer에 대입했다.

+근데.. 그럼 테스트1에서 leo는 어떻게 잘 출력된거지?

Troubleshooting 2

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<Integer, String> partici = new HashMap<>();
        
        for(int i =0; i<participant.length; i++) {
            partici.put(i,participant[i]);
        }
        
        for(int i=0; i<completion.length; i++) {
            partici.values().remove(completion[i]);
        }

        Collection<String> temp = partici.values();
        Iterator iter = temp.iterator();
        answer = iter.next().toString();
        return answer;
    }
}

문제

다른 테스트 케이스에서 시간초과가 났다.

원인

partici.values().remove(completion[i]); 이 부분에서 성능 문제가 발생한다.
왜냐하면 values().remove()는 매번 O(n)의 시간 복잡도를 갖기 때문에 이 부분을 completion의 길이만큼 반복하면 O(n^2)의 시간 복잡도가 되어 매우 느려진다.

정확히는 remove(Object o)를 할 때, values()의 결과인 컬렉션을 처음부터 끝까지 순회하는 과정에서 O(n)의 시간복잡도를 갖는다.

O(n^2)이면 100,000^2이므로 10,000,000,000이다.
100억이면 약 100초가 걸린다.

해결

아래 방법으로 로직자체를 개선해보자.

1. HashMap<String, Integer> 타입을 사용하여 참가자의 이름을 key로, 그 이름이 몇 번 나왔는지를 value로 저장합니다.
2. participant 배열을 순회하면서 참가자의 이름이 몇 번 나왔는지 카운트합니다.
3. completion 배열을 순회하면서 완주한 참가자의 카운트를 감소시킵니다.
4. 마지막으로 HashMap을 순회하면서 value가 1 이상인 key를 찾아 반환합니다.

2번 : O(n)
3번 : O(n)
4번 : O(n)

따라서 총 시간복잡도는 O(n)으로 10만번의 연산이 수행된다면 해결 될 것으로 보인다.

제출 코드

import java.util.*;
import java.util.Map.Entry;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> count = new HashMap<>();
        
        for(int i =0; i<participant.length; i++) {
            count.put(participant[i], count.getOrDefault(participant[i], 0) +1);
        }
        
        for(int i=0; i<completion.length; i++) {
            count.put(completion[i], count.get(completion[i])-1);
        }
         
        count.values().removeIf(sum -> sum==0);
        
        Iterator<String> iter = count.keySet().iterator();
        answer = iter.next();
    
        return answer;
    }
}

Troubleshooting 2에서 바꾼 로직의 4번을 어떻게 해결할지 고민이 참 많았다.

values()로 뽑고 값이 1인걸 탐색하면, 찾느다고 해도 1인 객체의 키를 가져올 수 없다.
그래서 찾아보다가 선택한 방법이 removeIf()를 사용해서 값이 0인것은 다 지우는 것이다.
그럼 또 남은 하나의 키를 어떻게 뽑을 것인가..
keySet()을 사용해서 iterator를 활용할 수 있게했다.

다른 풀이

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;
    }
}

keySet()을 이런식으로 활용하면 깔끔하구나 배워간다.