[Hash] 완주하지 못한 선수 - Java 풀이 (3가지 풀이 - map, set, 배열)

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

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

 

문제

 

풀이

해시맵, 배열, 해시셋 3가지 방법으로 각각 풀어보았다.

각각의 풀이는 결국 완주자배열에서 참여자이름이 없는 경우를 찾으면 되는 간단한 문제이다.

 

1) HashMap

import java.util.HashMap;
class Solution {
/*
	정확성  테스트
    테스트 1 〉	통과 (0.03ms, 77.6MB)
    테스트 2 〉	통과 (0.07ms, 75.1MB)
    테스트 3 〉	통과 (0.21ms, 81.7MB)
    테스트 4 〉	통과 (0.73ms, 81.5MB)
    테스트 5 〉	통과 (0.40ms, 80.1MB)
    효율성  테스트
    테스트 1 〉	통과 (29.38ms, 81.4MB)
    테스트 2 〉	통과 (49.72ms, 93.8MB)
    테스트 3 〉	통과 (53.20ms, 94.6MB)
    테스트 4 〉	통과 (54.15ms, 95.2MB)
    테스트 5 〉	통과 (68.88ms, 95.7MB)
*/
    public String solution(String[] participant, String[] completion) {
        HashMap<String ,Integer> h = new HashMap<String ,Integer>();
	    int tmp=0;
		for(String s: completion) {
	    	if(h.get(s) != null) {
	    		tmp = h.get(s);
	    		h.put(s,tmp+1);
	    	}
	    	else
	    		h.put(s,1);
	    }
		for(String s:participant) {
			if(h.get(s) != null) {
	    		tmp = h.get(s);
				if(tmp>0)
					h.put(s,tmp-1);                
				else
					return s;
			}
			else
				return s;
		}
		return "Error";
    	
	}
}

 

완주자 리스트를 hashmap에 count 해주면서 넣어주고,

for문을 통해, 참가자배열에서 완주하지못한사람을 찾아내기 위해

count를 빼주어 0인 경우나, null인 경우를 찾아 Return 해주었다.  

 

2) Arrays

public static String solution_withArray(String[] participant, String[] completion) {
		/*
		정확성  테스트
		테스트 1 〉	통과 (12.02ms, 78.8MB)
		테스트 2 〉	통과 (12.27ms, 76.2MB)
		테스트 3 〉	통과 (12.84ms, 77.9MB)
		테스트 4 〉	통과 (14.42ms, 83.7MB)
		테스트 5 〉	통과 (13.94ms, 87.1MB)
		효율성  테스트
		테스트 1 〉	통과 (149.44ms, 84MB)
		테스트 2 〉	통과 (263.91ms, 89.2MB)
		테스트 3 〉	통과 (361.44ms, 94.9MB)
		테스트 4 〉	통과 (308.02ms, 95.3MB)
		테스트 5 〉	통과 (340.47ms, 96.5MB)
	*/
        Arrays.sort(participant);
        Arrays.sort(completion);
        for(int i=0;i<completion.length;i++) {
        	if(!participant[i].equals(completion[i])) {
        		System.out.println(participant[i] +" "+completion[i]);
        		return participant[i];
        	}
        }
        return participant[participant.length-1];
    }

 

3) HashSet - 오답

public static String solution_hashset(String[] participant, String[] completion) {
        // set은 동명이인에 대한 count가 필요하므로 풀이 불가능
		HashSet<String> set = new HashSet<String>();
		for(String s : completion) set.add(s);
		for(String s : participant) if(!set.remove(s)) return s;
        return "";
    }

첫시도때에 기록이다

간단히 짜보려 했는데, 동명이인에 대한 처리가 필요해서 해시맵으로 전환했다.  

 

 

 

https://bangu4.tistory.com/179

[자료구조] Hash란? Java로 구현코드