프로그래머스 - 해시 완주하지 못한 선수 풀이(ArrayList를 이용한 풀이와 HashMap을 이용한 풀이 차이점)

시작하기, 뭐든 - 기록 23일차

 

오늘 푼 코딩테스트는 해시를 이용해서 풀어야하는 "완주하지 못한 선수"를 찾는 문제.

해시로 풀어야했으나 무시하고 for문으로 풀었더니.. 답은 나오나 효율성 테스트를 통과하지 못했고...

(그래서 오늘도 코딩뿌시기라는 말을 못썼고...)

 

HashMap으로 깔끔한 풀이를 봐서, 내가 이해한걸 바탕으로 최대한 세세하게 적어보려고한다.

(난 항상 이해가 어렵기 때문에...)

 

일단, 이 문제를 왜 해시로 풀어야하는지부터 차근차근 이해해보자.

나는 for문으로 풀긴 했지만, for문처럼 ArrayList도 index가있으니 List와 Hash를 비교해보려고 한다.

 

1. ArrayList

ArrayList는 잘 알다시피 index를 가지고 있다.

순차적으로 데이터가 들어가고, 역시 순차적으로 보여진다. index값을 알고있지 않으면 하나하나 순차적으로 index값을 통해 접근해야한다.

 

참가자와 완주자를 찾는 경우, sort를 통해 정렬해주지 않는 이상은 위에 표 처럼 맞는 값을 찾을 때까지  이중 for문을 돌려야한다. 

 

즉, ArrayList는 순서가 중요할 때 이득이 된다.

이 문제에 경우는 완주하지 못한 한명을 찾는거기 때문에, ArrayList에서 sort로 정렬한 다음 값이 다른 하나를 찾으면 풀 수 있기도 하다.

sort로 순번을 맞춰줘서 "순차적인 검사"가 의미있게 만들어줘서 가능하다. 실제로 프로그래머스 다른 풀이에도 해당 답안으로 푼 경우가 꽤 되는거 같다.

앞에서부터 index별로 검사하다가 값이 다른 첫번째 경우가 완주하지 못한 한명이 되기 때문이다.

 

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i;
        for ( i=0; i<completion.length; i++){

            if (!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        return participant[i];
    }
}

 

하지만 완주하짐 못한 사람이 두명, 세명, 그 이상이 된다면..??

이때는 sort해서 만든 index도 의미가 없어지기 때문에 ArrayList로는 머리가 아플 수 있다.

 

2. HashMap

이 문제가 "해시"로 풀라고 힌트를 준 이유가 있다.

HashMap은 "key"와 "value"로 이루어져있다. 이제 index, "순차적" 이런거에서 자유로워질 수 있다는 뜻이다!

Map이기 때문에 key값만 알아도 값을 불러올 수 있다.

그렇다면, 이 경우 사람 이름으로 비교해야 하기 때문에 이름으로 key값을 정해야한다.

이런식으로 key를 이름으로 잡는다. 그럼 이제 value를 어떻게 정하느냐가 문제다.

지금이 바로 Map의 매력적인 부분을 사용할 때다!!

Map은 key값이 같으면 해당 key 값을 찾아서 변경을 해준다.

즉 참가자 이름으로 key값으로 넣어줄 때 +1을 value에 넣어주고, 완주자 이름으로 key값을 넣을떄 -1을 해주면 완주한 사람 이름에는 0 값이 남게된다!

완주하지 못한 "leo"는 완주자명단에 없기 때문에 완주자 이름 key값으로 -1씩 해줄 때 빠지게 된다.

그런고로, 0이 아닌 애들을 찾으면 완주못한 사람을 찾을 수 있다는 뜻!!

 

여기서 잠깐! Map에서 이 부분이 왜 매력적이라 했는지 이유가 남았다!!

사람 이름이기 때문에 항상 고려해야할 부분인 "동명이인" 부분도 Map에서 해결되기 때문이다.

위에 예시처럼 "filipa" 동명이인이 4명일 때, "filipa" 한명만 완주하지 못했을 때의 경우다.

이럴 때도 역시 Map을 이용하면 문제가 없다.

 

이 문제는 이렇게 접근했어야 했고, 이해에 도움이 된 코드도 남겨두겠다.

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

여기서 사람 이름을 key값으로 했을 때 +1 해주는 부분이 이 부분이다.

hm.put(player, hm.getOrDefault(player, 0) + 1)

이 부분에서는 getOrDefault 함수의 쓰임을 알아야 한다.

 

getOrDefault(Object key, V DefaultValue)

- key : Map에서 value 찾을 때 쓰는 key값을 의미한다.

- defaultvalue : key값으로 value를 찾지 못했을 때 설정해주는 값

 

이것도 이해하는데 꽤 걸렸다. 예시를 보는게 최고인듯..

해당 코드의 뜻은 일단 이렇다.

 

hm.getOrDefault(player, 0) + 1
-> player 이름을 key로 가지고 있는 value값이 없으면 0으로 설정

for문을 돌면서 key값으로 "filipa"일 때를 살펴보자. 현재 참가자 HashMap에는 filipa를 key로 가진 값이 없다. 그렇기 때문에 defaultValue에서 설정해준 0을 넣어준다.

그리고 0으로 설정한 값에 +1을 해줘서 넣어주기 때문에 1이 된다.

 

계속 for문을 돌면서 다른 "filipa"를 만났을 때가 됐다.

이때 filipa를 key로 가진 value는 이미 1로 들어있다. 그렇다면 filipa의 value인 1을 가지고 온 다음 거기에 +1을 더해줘서 2가 된다.

 

getOrDefault 함수는 이런식으로 이해하면 된다.

 

이 한문제로.. 참 오랜 시간에 걸렸지만 그래도 Map을 조금이나마 이해할 수 있는 시간이 되어 기...기..기쁘...

 

끝!