문제 설명

마라톤에 참여한 사람 목록(배열)과 완주한 사람 목록(배열)이 주어졌을 때, 완주하지 못한 사람을 찾는 문제이다.

• 제한 사항
  • 경기 참여자 수는 1~100,000
  • 참여 목록(participant)의 수는 완주자 목록(completion) 보다 1 크다
  • 참가자의 이름은 1부터 20 이하의 알파벳 소문자이다.
  • 참가자 중에는 동명이인이 있을 수 있다.

문제 링크 : 완주하지 못한 선수

풀이

본 문제는 경기 참여자 수가 최대 100,000으로 참여자 목록과 완주자 목록을 이중포문을 통해 무차별 비교를 한다면 최악의 상황으로 100,000*100,000 즉 1억번(컴퓨터에서 1초 걸리는 연산) 이상의 반복이 발생하기 때문에 되도록 100,000을 한번만 반복하여 처리하도록 만들어야 한다.

따라서 각각의 목록을 비교만 하면 되기 때문에 Map 자료구조를 사용하여 참여자들을 모두 Map에 등록하고 완주자 목록을 순회하면서 기존 Map에 중복된 참여자를 제거해주면 완주하지 못한 인원이 나오게 된다. Set을 사용하지 않은 이유는 동명이인 처리를 카운팅하기 위해서 였다.

코드

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
        for(String str : participant) {
            int cnt = 1;
            if (map.containsKey(str)) {
                cnt = map.get(str) + 1;
            }
            map.put(str, cnt);
        }
        for(String str : completion) {
            if (map.containsKey(str)) {
                map.put(str, map.get(str) - 1);
                if (map.get(str) == 0)
                    map.remove(str);
            }
        }
        String s = String.valueOf(map.keySet());
        return answer = s.substring(1, s.length()-1);
    }
}