Programmers / Level 1 / 완주하지 못한 선수 (*Hash 알고리즘)

[문제설명]

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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.ArrayList;
import java.util.Arrays;

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

 

처음에 간단하다고 생각한 문제였는데, 동명이인 조건이 좀 어려웠다.

어차피 완주를 못한 사람은 한 명이고, participant와 copmpletion의 길이가 1만 차이나기 때문에

sort를 사용해 두 배열을 정렬하면, 완주하지 못한 사람을 찾을 수 있게 된다.

 

다만, 

participant 배열의 가장 뒤에 있는 선수가 완주하지 못한 경우를 고려해야 한다.

completion배열을 다 돌 때 까지 완주하지 못한 선수를 찾지 못했다면,

participant 배열의 가장 끝에 있는 선수가 완주하지 못한 선수가 된다.

 

---

 

Hash 를 이용하는 문제인 것 같아, Hash로 코드를 짠 사람들의 코드도 보고 

Hash 알고리즘이 익숙하지 않아 찾아봤다.

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        // HashMap 생성
        HashMap<String, Integer> map = new HashMap<>();
        for (String player : participant) {
            map.put(player, map.getOrDefault(player, 0) + 1); // key는 player, value는 이전 값에 +1한 값
            // getOfDefault : map에서 player란 key를 가진 값을 가져달란 것! 
            // player가 아직 없으면 0을 달라! 즉, 이전에 없었으면 0+1=1로 set, 있으면 선수 값 가져와 +1 해 map에 넣어달란 것
        }
        // 완주자 목록에 있는 선수 빼기
        for (String player : completion) {
            map.put(player, map.get(player) - 1); // player가 갖고있는 값 가져온 후, -1
        }

        // value가 0이 아닌 선수가 완주 못 한 선수
        // keySet 사용 (map의 keySet을 통해 map이 갖고있는 key를 꺼냄)
        for(String key : map.keySet()) {
            if(map.get(key) != 0) {
                answer = key;
                break;
            } 
        }

        return answer;
    }
}