[Java] 완주하지 못한 선수

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

 

문제 접근

일반적인 접근

1. 완주자 명단으로 해쉬맵 만듬

2. 참가자 명단 돌면서 없는 사람 찾음

 

위와 같이 접근하면 큰일 난거다.(맞다 나다!)

 

주의 사항 중 "동명이인이 존재한다" 이걸 명심해야한다.

항상 실수하는 것이 나 혼자서 제약사항의 범위를 결정해버리는 것이다...

 

테스트 케이스에는 참가자 명단에만 동명이인이 있다.

그렇다. 나는 완주자 명단에도 동명이인이 존재할 수 있다는 것을 고려를 안했다.

 

다음은 동명이인이 참가자 및 완주자 명단에 있는 것을 고려한 접근법이다.

1. 완주자 명단을 순회하며 해쉬맵을 만듬 (key: 이름, value: 동명이인 숫자)

1-1. 순회할 때, 이미 같은 이름이 있으면 값을 +1해서 갱신

2. 참가자 명단을 순회하며 해쉬맵에 이름이 존재하는지 확인

3. 이름이 존재하면, 값을 -1함

3-1. 값이 0보다 작으면 완주하지 못한 사람이므로 return

3-2. 값이 0보다 크면 -1한 값으로 해쉬맵을 갱신

4. 이름이 존재하지 않으면, 완주하지 못한 사람이므로 return

 

소스 코드

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
        
        for (String name : completion) {
            if (map.containsKey(name)) {
                map.put(name, map.get(name) + 1);
            } else {
                map.put(name, 1);
            }
        }
        
        for (String name : participant) {
            if (map.containsKey(name)) {
                int count = map.get(name) - 1;
                if (count < 0) {
                    return name;
                } else {
                    map.put(name, count);
                }
            } else {
                return name;
            }
        }
        return answer;
    }
}