[ps] 완주하지 못한 선수

https://programmers.co.kr/learn/courses/30/lessons/42576

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였다. 단 한 명의 선수를 제외하고는 반드시 모든 선수가 마라톤을 완주한다. 마라톤에 참여한 선수들의 이름과 완주한 선수들의 이름이 담긴 배열이 각각 주어지는 경우 완주하지 못한 선수를 찾아야 한다.

문제의 조건은 다음과 같다.

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100000명 이하이다.
• 완주자는 참여자보다 1명 적다. 즉, 한명을 제외하고 모두 완주한다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 구성된다.
• 참가자 중에는 동명이인이 있을 수 있다.

문제 풀이

import java.util.*;

public class Main {

    public static class Solution {

        public String solution(String[] participants, String[] completions) {
            Map<String, Integer> map = new HashMap<>(completions.length);

            for (String completion : completions) {
                map.merge(completion, 1, Integer::sum);
            }

            for (String participant : participants) {
                Integer value = map.get(participant);

                if (value == null || value < 1) {
                    return participant;
                }

                map.put(participant, value - 1);
            }

            return null;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(
                new String[]{"mislav", "stanko", "mislav", "ana"},
                new String[]{"stanko", "ana", "mislav"}
        );
    }

}

해시 자료구조를 사용하면 간단히 구할 수 있다. 이름을 키로 사용하고 동명이인이 참가하는 경우를 위해서 값으로 인원수를 저장한다. 동일한 이름(키)의 참가자가 참여하는 경우 인원수를 증가 시킨다. 참가자를 모두 저장한 후, 완주자 명단을 순회하며 인원수를 감소시키면서 완주하지 못한 참가자를 구할 수 있다.