[JAVA] 완주하지 못한 선수 - HashMap

같은 테스트를 두번 하는건 힘들어요.. (Photo by Snapwire)

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

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

https://snoop-study.tistory.com/2

[JAVA] 완주하지 못한 선수 - ArrayList

저번에는 ArrayList로 풀어서 시간 초과로 실패해버렸는데 이번에는 hash로 풀어보았습니다.

덕분에 HashMap을 실전에서는 처음 써본 것 같네요ㅎㅎ ArrayList보다 훨씬 쉬웠습니다.

시간복잡도는 O(N)입니다.

 

구현

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        //HashMap 선언
        HashMap <String, Integer> map = new HashMap <String, Integer>();
        
        //완주자 저장
        for(int i=0;i<completion.length;i++){
            if(!map.containsKey(completion[i]))
                map.put(completion[i], 1);
            else
                map.put(completion[i], map.get(completion[i])+1); //hash 업데이트
        }
        
        for(int i=0;i<participant.length;i++){
            //이름이 key값에 존재하지 않음 -> 완주 못함 1
            if(!map.containsKey(participant[i])){
                answer = participant[i];
                break;
            }
            else{
                int num = map.get(participant[i]);
                if(num == 0){
                    //이름이 key값에 존재하지만 카운트 0 -> 완주 못함 2
                    answer = participant[i];
                    break;
                }
                //체크한 참가자는 제거
                map.put(participant[i], map.get(participant[i])-1);
            }
        }
        return answer;
    }
   
}

 

두 번만에 통과,,

 

참고

https://snoop-study.tistory.com/4

[JAVA] HashMap 사용법 정리