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

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

 

나의 풀이

    /* 힌트보고 재작성 */
    public static String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String,Integer> participantMap = new HashMap<>();
        
        for (String partName : participant) {
            participantMap.put(partName, participantMap.getOrDefault(partName, 0)+1);
        }
        
        for (String compName : completion) {
            participantMap.put(compName, participantMap.get(compName)-1);
        }

        for(String name : participantMap.keySet()){
            if(participantMap.get(name) == 1){
                answer = name;
            }
        }
        System.out.println("###  answer : "+answer);
        return answer;
    }

    /* ArrayList를 활용 -> 라인은 줄었지만, 성능에서 또 걸림 */
    public static String solutionSecond(String[] participant, String[] completion) {
        String answer = "";
        List<String> participantList = new ArrayList<>();
        for (String person : participant) {
            participantList.add(person);
        }
        for (String comp : completion) {
            participantList.remove(comp);
        }
        answer=participantList.get(0);
        System.out.println("###  answer : "+answer);
        return answer;
    }

접근 방법

처음에 중첩 loop를 사용해서 하나씩 제거하는 방법을 생각했지만, 시간이 오래걸려서 채점에서 CUT
힌트를 보고서야 이 문제가 해시를 이용한 문제라는걸 알았다...
처음엔 Hash Set 을 이용했지만, 중복이 없어지는 Hash의 특성으로 계속 막혀서 결국 힌트를 봤다.

다른 사람의 풀이를 슬쩍 봤는데, 성능을 위해 해시를 쓰되, 중복처리를 위해 맵을 이용해 count를 하는게 인상깊었다

다른 사람의 풀이

HashMap 사용

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

Sorting 사용

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

비록 해시 문제이지만,  개인적으론 풀이법은 아래가 좀 더 멋져보인다

느낀점

일단, 어떤 문제든 일단 중첩 loop로 접근하는 나를 보며, 아쉬웠다

이번에 적절한 자료구조를 찾는게 힘들었다. Hash 까지는 문제를 보며 찾아갔지만, 풀이를 보고서야 HashMap을 쓰는 이유를 알게 되다니..

성능을 위해서 Hash를 사용했고

중복 체크를 위해 Map을 사용했다 

getOrDefault() : map에서 get을 하되 없을때 default 값 지정가능

 

그외의 방법으로는 Array로도 Sorting을 사용하면 시간안에 해결이 가능했지만,

해시에 집착하다보니 Sorting을 더 생각해보지 못해 아쉽다

여러개의 목록에서 중복/여부 체크시 -> Array라면 Sorting 해서 접근하는 방법도 좋을듯하다

 

비슷한 유형

[프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
[프로그래머스] 전화번호 목록 (해시 Lv. 2)
[프로그래머스] 위장 (해시 Lv. 2)
[프로그래머스] 베스트 앨범 (해시 Lv. 3)