[자바 알고리즘 인터뷰] ch 11 해시 테이블 (5) 완주하지 못한 선수

 

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

프로그래머스

 

 

 

 

 

 

풀이 1) 해시 테이블을 이용한 풀이 

 

- 참여한 선수 배열에서 완주한 선수 배열을 제외하면 1명이 남으며, 이 값을 찾아내는 문제다. 

- 동명이인이 등장할 수 있으므로, 이름을 키로 인원을 값으로 한 해시 테이블로 처리하여 동명이인인 경우에는 해당 키의 값을 +1 해준다. 

 

- 그런 다음 완주한 선수의 이름을 추출해 해시맵에서 하나씩 삭제하면 된다. 값을 -1 하다가 만약 1인 경우 해시맵에서 삭제하도록 처리한다. 

 

- 이 문제는 반드시 1명만 남는다는 제약 조건이 있으므로, 이렇게 하면 해시맵에는 유일하게 완주하지 못한 선수만 남을 것이다. 마지막으로, 남아 있는 항목의 키를 리턴하면 된다. 

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        
        //참여 선수 이름, 동명이인인 경우 +1 해시맵 삽입
        for(String p : participant) 
        {
            map.put(p, map.getOrDefault(p,0)+1);
            
        }
        
        //완주 선수 이름 제거 
        for(String c : completion)
        {
            int left = map.get(c);
            if(left==1) //하나만 있는 경우 키 자체를 삭제
                map.remove(c);
            else
                map.put(c,left-1);
        }
        
        //남아 있는 유일한 키(이름) 리턴
        return map.entrySet().iterator().next().getKey();
    }
}