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

홈런볼·2023년 7월 5일

프로그래머스

목록 보기

7/36

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42862

문제접근

participant를 map에 넣고, Map을 순회하면서 completion의 요소를 제거한다. 그리고 participant 함수에 남아있는 값을 리턴하는 방식으로 접근했다.
Map의 get 함수 시간복잡도가 O(1) 이기 때문에 Map 자료구조를 이용하는게 맞다고 생각했다.

1차시도 - 실패

public String solution(String[] participant, String[] completion) {
        HashMap<Integer,String> hm = new HashMap<>();
        for(int i=0;i<participant.length;i++) hm.put(i,participant[i]);

        int index = 0;
        for(int k=0;k<completion.length;k++){
            for(int key:hm.keySet()) {
                if(completion[k].equals(hm.get(key))) {
                    hm.remove(key);
                    break;
                }else{
                  index = key;
                }
            }
        }
        return hm.get(index);
    }

정확성 테스트

정확성 테스트는 통과했지만, 효율성 테스트는 시간초과가 발생하였다.
completion을 순회하면서 keySet으로 접근하는데, 이 경우 처음 completion 배열의 값이 participation에 없는 경우 시간복잡도 o(n)이 소요되기 때문에 효율성 테스트에서 시간초과가 발생한 걸로 추측된다.

2차시도 - 실패

이전과 동일하게 hashmap을 사용했다. remove 함수의 경우 hashmap의 길이가 길어지면 최악의 경우 O(n)이 발생하기 때문에 remove 함수를 사용하지 않고, value 값을 이용해서 완주못한선수를 찾는 방법으로 방식을 변경했다.

public String solution(String[] participant, String[] completion) {
        String answer="";

        HashMap<String,Integer> hm = new HashMap<>();
        for(int i=0;i<participant.length;i++){
            int val = hm.getOrDefault(participant[i],0);
            hm.put(participant[i],++val);
        }
        for(int i=0;i<completion.length;i++){
            int val = hm.getOrDefault(completion[i],0);
            hm.put(completion[i],--val);
        }
        for(String key:hm.keySet()){
            if(hm.getOrDefault(key,0) != 0) answer = key;
        }
        return answer;
    }