[알고리즘] 프로그래머스 완주하지 못한 선수 자바 JAVA 해시

 

 

 

처음에 반복문 두개 겹쳐서 하다가 효율성에서 떨어졌다. 리스트로 해보려다가 어차피 효율성에서 떨어지다가 두 배열을 정렬하고 다른거 찾으면 answer에 넣게 만들었다. 

 

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

        Arrays.sort(participant);
        Arrays.sort(completion);

        for (int i = 0; i < completion.length; i++) {
            if (!participant[i].equals(completion[i])) {
                answer = participant[i];
                break;
            }
        }

        if (answer.equals(""))
            answer = participant[participant.length - 1];

        return answer;
    }

하고 다른 분의 답을 봤는데, 나처럼 푼사람이 계셨다. 하지만 댓글을 보니 루프를 총 3번 돌리니 좋은 방법은 아니라는 이야기가 있었다.

 

다들 해시해시 그러길래 보니 제목 밑에 해시라고 적혀있었다.(!!) 그래서 검색해보니 위처럼 푸신분이 많았다. 그래도 해시로 해보자는 생각으로 밑의 코드를 가져와봤다.

 

    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> hash = new HashMap<>();
        
        for (String s : participant)
            hash.put(s, hash.getOrDefault(s, 0) + 1);
            
        for (String s : completion)
            hash.put(s, hash.get(s) - 1);

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

        return null;
    }

해시를 안해봤으면 처음엔 뭐지 싶을 수도 있다. hash는 key와 value가 쌍으로 이루어져있는데 key는 유일하지만 value는 여러개 가능하다. 문자열을 key로 두고 같은 키마다 +1을 해주는 것이다. 그리고 완주자를 찾을때마다 -1일 해줘서 0이 아닌 사람은 완주를 못한 사람이라고 간주하고 return 하는 것이다. 당연한 이야기이지만 hash로 하는게 3배이상 빠르다고 한다.