[JAVA] 해시 "완주하지 못한 선수"

첫번째 방법

필자가 처음에 사용한 방법은 이러하다.

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        for(int i = 0; i<participant.length; i++){
            for(int j = 0; j<completion.length; j++){
                if(participant[i].equals(completion[j])){
                   participant[i]="";
                }
            } 
        }
        for(int i = 0; i<participant.length; i++){
            if(participant[i] != ""){
               answer=participant[i];
            }
        }
        return answer;
    }
}

이중for문을 이용해서 하나씩 값을 비교해서 NULL값을 넣어주려고햇지만 nullpoint error가 떠서 ""로 바꿔주었다.

그리고 ""인 항목이 아닌 중복되지 않은 남은 1개의 participant(완주하지 못한 선수)를 answer에 넣어주었다.

 

이렇게 했더니 O(n^2)이므로 시간 초과가 발생했다.

 

 

두번째방법

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Arrays.sort(participant);
        Arrays.sort(completion);
        int i =0;      //a
        for(i =0; i<completion.length;i++){
            if(!participant[i].equals(completion[i])){
                return participant[i];
            }   
        }
        return participant[i];
    }
}

정렬을 하고 for문을 통해 같은 순서대로 정렬된 이름을 차례대로 비교하다가,

중간에 다른 사람을 발견하면 바로 리턴한다.

이 경우 O(n)이므로 시간초과가 발생하지 않는다.

 

 

세번째방법

*참고 : 이진탐색은 O(log N)이므로 < O(N) < O(N^2)이다.

*HashMap 관련 글 + HashMap 메모이제이션 참조 http://tech.javacafe.io/2018/12/03/HashMap/

자바 HashMap을 효과적으로 사용하는 방법

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        
        //참가자(key)들은 모두 value값을 1로 설정하여 Map에 put해준다.
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);

        //완주자(key)들은 참가자와 동일한 이름을 가졌으면 덮어쓰기로 (기존 value값-1)이 put해준다.
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
                break;//답을 찾으면 반복문 중지해주는 센스! 혹은 바로 return해버리기.
            }
        }
        return answer;
    }
}

위의 주석을 참고하여 HashMap을 이용하여 중복된 Key값은 덮어쓰기하여,

덮어쓰기가 되지 않은 Key의 "Value값을 비교"하여 덮어쓰기 되지 않은 Key(완주하지 못한사람)을 반환한다.

 

여기서, 포인트가 있다.

hm.put(player, hm.getOrDefault(player, 0) +1);

위 부분은 단순히 put메소드가 아닌 getOrDefault메소드를 통해서 이미 Hash값에 등록된 key값이 있으면 그 key의 value를 가져온다.

 

예를들어, 동명이인 Alice(1), Alice(2)가 있으면 이미 Alice(1)을 넣은 상태로 (Alice, 1)의 Map이 생성된 상태이다. 이때 hm.put("Alice", getOrDefault( "Alice", 0) =1 +1)을 반환하여 (Alice, 2)로 덮어쓰기가 된다.

동명이인인 경우는 Value값이 2를 갖게 되는것이다.

 

이를 통해 중복된 Hash값을 체크할때 사용할 수 있음을 알 수 있었다.