10. 프로그래머스 - 완주하지 못한 선수 (해시)

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와
완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,
완주하지 못한 선수의 이름을 반환하는 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"

 

입출력 예 설명
예제 1: "leo"는 참여자 명단에 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 2: "vinko"는 참여자 명단에 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 3: "mislav"는 참여자 명단에 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

 

---

먼저 하나하나 대조하면서 찾는 방법은 O(N^2)이어서 경기에 참여한 선수는 최대 10만명으로 가정했기 때문에 테스트 케이스를 통과하지 못할 것이다. 따라서 이것보다 더 나은 O(logN)이나 O(N)의 알고리즘을 찾아야 한다.

 

 

1. 완주한 선수들의 이름을 해시맵에 추가하되, 키-값은 이름-이름 개수로 한다.

2. 참가자들의 이름을 해시맵에서 찾아 값을 1씩 줄인다.

3. 2번 과정 중에 해시맵에서 값이 0이거나 혹은 해시맵에 없는 선수의 이름을 찾으면 답으로 반환한다.

 

이렇게 구현하기 위해 필요한 메서드가 바로 아래의 메서드이다.

 

getOrDefault()

- 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드

 

 

• get()을 사용할 경우, 키가 없으면 null을 반환
• null 처리 없이 기본값으로 대체하고 싶을 때 getOrDefault()가 유용

 

사용 방법

getOrDefault(Object key, V DefaultValue)

매개 변수 : 이 메서드는 두 개의 매개 변수를 허용합니다.

• key : 값을 가져와야 하는 요소의 키이다.
• defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야 하는 기본값이다.

반환 값 : 찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환됩니다.

 

알고리즘 코드

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> hm = new HashMap<>();

        for(String str : completion) {
            hm.put(str, hm.getOrDefault(str, 0) + 1);
        }
        
        for(String str : participant) {
            if(hm.getOrDefault(str, 0) == 0) {
                return str;
            }
            hm.put(str, hm.get(str) - 1);
        }
        
        return null;
    }
}

 

시간 복잡도 분석

완주한 선수들의 이름을 해시맵에 추가하는 연산의 시간 복잡도는 O(K)이고, 참가자의 이름을 해시맵에서 제외하는 연산의 시간 복잡도는 O(N)이다. 추가로 completion의 최대 길이는 N - 1이므로 K 대신 N - 1로 대체하면 시간 복잡도는 O(2 * (N - 1))이다. 따라서 최종 시간 복잡도는 O(N)이 된다.