💛 오늘의 학습 키워드

[해시] 완주하지 못한 선수

📝 문제

문제 설명

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

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

제한 조건

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

💬 내 풀이

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);

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

💻 내 접근 방법

1. 일단 sort() 함수를 사용해서 배열을 정렬한다.
2. for() 반복문을 사용해서 같지 배열의 값이 서로 같지 않을 때까지 찾는다.
3. 같지 않을 때 break를 사용해서 멈추고, 해당 값을 return 하는 방식으로 구현했다.

✨ 다른 사람 풀이

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        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){
                return key;
            }
        }
        return “”;
    }
}

1. HashMap 객체를 생성해서 put()메소드를 사용하여 key는 participant의 선수이름을, value에는 key값으로 value를 찾고 1씩 증가하도록 한다.

• getOrDefault() : key를 통해 value를 찾을 때 value 값이 null 이면, 대신 기본 값을 반환하도록 하는 메소드

getOrDefault() 와 비슷한 메소드 Optional.ofNullable().orElse() 예제

Map<String, String> map = new HashMap<>();
map.put("blue", "파랑");
map.put("purple", "보라");
Optional.ofNullable(map.get("red")).orElse("디폴트값")); 

2. 똑같이 completion의 선수이름으로 value 값을 찾고 -1씩 감소하도록 값을 넣어준다.

3. keySet()을 사용하여 key 의 집합을 뽑아내어 0이 아닌 값을 찾는다.

💦 회고

sort() 메소드를 사용하니 시간복잡도가 NlogN으로 늘어나는데, HashMap을 사용해서 단순한 count 기능으로 구현하니 O(n)의 시간복잡도를 가져, 효율성 테스트 성능이 월등하게 나오는 것을 확인하게 되었다.
자료구조를 잘 이용하는 게 중요하다!

시간 복잡도 빠르기
$O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(2^N) > O(N!)$

참고
https://gymdev.tistory.com/m/39