3-2 완주하지 못한 선수

유태형·2022년 4월 29일

Java 알고리즘 프로그래머스

알고리즘 - Java

목록 보기

4/32

문제

문제분석

N명의 참가자에서 N-1의 완주자를 제외한 낙오자가 누구인지 구하는 문제입니다.

풀이

중복 입력이 있는 문제는 Map을 사용하는지 한번 생각해 봐야 합니다. 이번문제에도 예제#3에서 mislav가 중복으로 동명이인 입니다. Map으로 문제를 푼다고 생각하면 아마도 participant를 모두 해시맵에 넣고 completion만큼 제외하면 남은 사람이 탈락자가 될것입니다.

Participant -> HashMap

		Map<String, Integer> players = new HashMap<>();
        
        O(n)
        for(String p : participant){
            players.put(p,players.getOrDefault(p,0) + 1);
        }

해시맵 players를 만들고 참가자들을 한명씩 players에 입력합니다.
맵.getOrDefault(키,디폴트)는 해당 키가 존재시 키를 반환하고 존재하지 않으면 디폴트값을 반환합니다.

HashMap에서 completion빼기

		for(String c : completion){
            int n = players.get(c) - 1;
            if(n==0) players.remove(c);
            else players.put(c,n);
        }

만약 0명이 되면 명단에 존재할 필요가 없습니다. 더이상 해당이름인 사람이 없는데 0인 상태로 있으면 나중에 탈락자를 찾는데 방해가 될 뿐입니다.
그래서 해당 이름의 사람수를 -1하여 가져와서 0명이면 해당 이름을 삭제합니다.
아직 남아있는 경우 단순히 -1만 합니다.

HashMap에서 낙오자 구하기

return players.keySet().iterator().next();

이미 0명인 이름은 모두 삭제했기 때문에 1명인 낙오자 이름만 남게됩니다 따라서 O(1)로 이터레이터로 남아있는 한명만 뽑아내면 정답입니다.

코드

import java.util.*;

class Solution {
        Map<String, Integer> players = new HashMap<>();
        
        //O(n)
        for(String p : participant){
            players.put(p,players.getOrDefault(p,0) + 1);
        }
        
        //O(n)
        for(String c : completion){
            int n = players.get(c) - 1;
            if(n==0) players.remove(c);
            else players.put(c,n);
        }
        
        //O(1)
        return players.keySet().iterator().next();
        
    }
}