완주하지 못한 선수 - Hash

문제

완주하지 못한 선수 - 출처 : https://programmers.co.kr/learn/courses/30/lessons/42576

풀이방법1. 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        List<String> participantList = new ArrayList<String>(Arrays.asList(participant));
        
        for(String completeMan : completion){
           if(participantList.contains(completeMan)==false){
               answer = completeMan;
           }else{
               participantList.remove(completeMan);
           }
        }
        
        if(answer.isEmpty()){
            answer = participantList.get(0);
        }
        
        return answer;
    }
}

List의 기능을 이용해보려고 배열을 리스트로 형변환후 진행하니, 정확성은 50, 효율성이0으로 계속 문제를 풀지 못했다.

 

리스트 - 효율성 0

제한사항에 참가자의 이름이 1개이상, 20개 이하의 소문자로 구성되어 있다는 문구가 왜 있지? 싶었었는데, 다른사람의 문제 풀이를 보고 이해가 갔다.

 

풀이 방법2)

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Arrays.sort(participant);
        Arrays.sort(completion); 
        
        for(int i=0; i<completion.length; i++){
            if(participant[i].equals(completion[i]) == false){
                answer = participant[i];
                break;
            }
        }
        if(answer.isEmpty()){
            answer = participant[participant.length-1];
        }
        
        return answer;
    }
}

초기, 배열을 모두 sorting 해서 순서대로 데이터를 나열한 다음, 비교하면 참가자가 동명이인이든, 아니든 순차적으로 정렬된 이후 비교하니까 좀더 빠르게 구할수 있었다.

리스트 - 효울성 50

 

# 여기서 핵심은 HASH문제라는거. ㅋㅋㅋㅋ 핳하하 

그래서 HASH를 사용한 다른사람 풀이를 보고 문제를 풀어보았다.

풀이방법3) - HASH

public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for(String partice : participant) {
            map.put(partice, map.getOrDefault(partice, 0)+1);
        }
        
        for(String complete : completion) {
            map.put(complete, map.get(complete)-1);
        }
        
        for(String key : map.keySet()){
            if(map.get(key)==1){
                answer = key;
                break;
            }
        }
                
        return answer;
    }		

HashMap - 키는 중복 허용하지 않기 때문에, 동명 이인이든 아니든 상관없이 value만 보고 완주하지 못한 친구를 찾을 수 있다. HashMap을 사용하니까 리스트보다 속도측면에서 확실히 빠른것을 확인 할 수 있었다.

Hash 사용

 

방법1은 알파벳순으로 정렬없이 리스트의 값을 비교해서 O(n)의 복잡도를 가짐

방법2는 정렬 후 비교하여, 이진탐색이 가능하여 O(log n)의 시간이 걸림.

방법3은 key-value의 Map을사용하여 O(1)의 복잡도를 가짐.

 

* Map interface의 getOrDefault(키값, 기본값)을 기억하자!