[프로그래머스/JAVA] 완주하지 못한 선수 - 해시

 

 

1. Sort

참여자와 완주자 Array를 정렬한 후 값을 비교하는 방법

입출력 예의 세번째 경우를 sort하면 

participant는  ana | mislav | mislav | stanko

                                                   ▼ --------------  일치하지 않음

completion는 ana | mislav | stanko

import java.util.Arrays;

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

 

 

2. Hash

하지만 이 문제는 해시문제이기 때문에 해시를 이용하여 풀어보았다. 먼저 HashMap의 특징을 이해해야 한다. 

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
		String result = null;
		HashMap<String,Integer> hm = new HashMap<String, Integer>();
			
		for(String p : participant) {
			hm.put(p, hm.getOrDefault(p, 0)+1);
		}

		
		for(String c : completion) {
			hm.put(c, hm.get(c)-1);
		}
		
		for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
            	result = key;
            }
        }
        return result;
		
	}
}

 

먼저 참가자가 key, 참가자 이름에 해당하는 수가 value인 hashMap에 참가자를 put 하였다. 

HashMap은 이미 존재하는 Key에 put하게 되면 새로 추가 되는게 아니라 기존 key에 해당하는 value가 바뀐다.

getOrDefault를 통해 key에 해당하는 데이터가 없을 경우 0을 세팅한 후 +1를 하고,  존재하면 기존값에 +1 시켰다.

첫번째 for문을 통과한 HashMap의 데이터를 출력해보면 아래와 같은 결과가 나타난다.

ana:1
mislav:2
stanko:1

 

그 다음으로 HashMap에 완주자를 put 하면 되는데, key에 해당하는 value를 조회하여 -1 하고, 다시 put 해준다.

완주자 목록에 있는 key만 value가 -1씩 되고, 0이 된 경우 완주한 것으로 판단하는 것!

(완주자는 참가자 명단에 속하므로 HashMap에서 get(key)하면 없는 경우가 없다.)

ana:0
mislav:1
stanko:0

 

따라서 value가 0이 아닌 key 찾아 출력하면 완주하지 못한 참가자를 구할 수 있다.