완주하지 못한 선수(해시)

코딩테스트 후 오답노트 식으로 작성해보려 한다.

 

< 시나리오 >

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

난 처음에 일단 participant의 값 중 completion에 포함 되어 있지 않는 값을 뽑아 냈다.

이렇게 되면 1, 2번 예제와 같은 경우는 잘 통과 할수 있으나 3번과 같은 중복 되었을 경우 실패한다.

따라서 나는 for문으로 part와 comp안에서 미리 비교된 값은 comp배열에서 빈값으로 만들어 주었다. 이러면 중복됐어도 한번 비교 시 빈값으로 바뀌기 때문에 다음에 중복된 값이 비교값으로 나와도 상관없어진다.

 

나의 풀이

public static String solution(String[] part, String[] comp) {
        String answer = "";
        String[] result = {};
        for(String p : part){
            System.out.println("comp: " + comp.toString());
            if(Arrays.asList(comp).contains(p)){
                for(int i=0 ; i< comp.length; i++){
                    if(comp[i].equals(p)){
                        comp[i] = "";
                    }
                }
                continue;
            }else{
                answer = p;
            }
        }
        System.out.println("answer : " + answer);
        return answer;
    }

근데 이러한 코드가 테스트에서는 통과 하지만 정확도와 효율성이 많이 떨어진다.

 

따라서 다른 사람 풀이를 토대로 다시 생각해보았다.

public static String solution(String[] part, String[] comp){
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        (1)for (String player : part) hm.put(player, hm.getOrDefault(player, 0) + 1);
        (2)for (String player : comp) hm.put(player, hm.get(player) - 1);

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

 

HashMap 에 대해서 잘 사용을 할 생각을 못했다.

위의 코드를 분석해보았다.

 

(1)과 같은 경우 part배열의 선수들의 중복 횟수를 체크 한다. 이때 getOrDefault를 사용하는데

• getOrDefault(key, defaultValue)의 경우 : 현재 hashmap의 key의 value가 존재할 경우는 해당 value 값을 사용하고 만약 존재하지 않는다면 지정해 둔 defaultValue를 사용한다.

따라서 , 모든 선수들은 기본값이 0+1 이기 때문에 1 씩 가지고 있고 , 중복된 선수들은 1 이상을 가지고있는다.

 

(2) 여기서 이제 완주한 선수 목록을 key로 hashmap 에서 value 값을 가져와 1씩 빼준다.

경기를 완주한 선수들은 중복없이 한명씩만 있기 때문에 hashmap 에 있던 값들은 대부분 1씩 가지고 있고 중복된 key의 value만 1이상 이였기 때문에 1씩 뺀 후에도 0 이 아닌 key 값이 완주 못한 선수의 이름이 된다.