[Level1] 완주하지 못한 선수

문제

---

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,

완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

해결 방법 : 배열의 정렬을 활용

---

 

public static String solution(String[] participant, String[] completion) {
	Arrays.sort(participant);
	Arrays.sort(completion);
	int index = 0;
	for(String c : completion) {
		if(!c.equals(participant[index]))
			return participant[index];
		index++;
	}
	return participant[participant.length-1];
}

참여한 사람들과 완주한 사람들을 담아둔 배열을 정렬시키고,

배열의 처음부터 순차적으로 비교해나가며 완주하지 못한 선수를 찾아내도록 만들었다. 

 

위의 코드는 완주한 사람을 배열에서 값을 순차적으로 가져와 같은 인덱스의 참여한 사람 배열의 값을 비교해 같은 값인지 확인한다.

equals() vs ==

String은 참조변수라서, ==으로 비교할 경우 객체가 같은가를 비교하게 되므로, equals를 사용하여 내용이 같은지 비교하도록 했다.

Arrays.sort() 시간 복잡도 : O(nlogn) or O(n^2) // O(nlogn)

primitive type배열은 Dual Pivot Quick Sort를 하고 nlogn을 기대할 수 있지만, 최악의 경우 n^2있고, primitive type은 comparator를 지정할 수 없다.

 

객체, 제너릭 타입들은 comparator를 지정하거나, null인 경우

Merge sort 또는 TimSort를 이용한다. 이는 최악의 경우에도 nlogn을 기대할 수 있다.

 

 

 

해쉬맵을 활용

---

public static String solution(String[] participant, String[] completion) {
	String answer = "";
    
	HashMap<String, Integer> prtcpt_map = new HashMap<>();
	for(String name : participant) {
		prtcpt_map.put(name, prtcpt_map.getOrDefault(name, 0)+1);
		// getOrDefault() : 값이 없으면 0으로 초기화하고 있으면 해당 값을 가져온다
	}
	
	for(String name: completion) {
		prtcpt_map.put(name,  prtcpt_map.get(name)-1);
	}
	
	for(String name: prtcpt_map.keySet()) {
		if(prtcpt_map.get(name) != 0) {
			answer = name;
			break;
		}
	}
	
	return answer;
}

동명이인이 있을 수 있어 참여한 사람의 이름과 명수를 K-V의 형태로 Map에 저장하고,

완주한 사람의 이름이 나올때 마다 명수를 줄여준다. 완주하지 못한 사람은 1명이기 때문에,

keySet을 받아와 key의 value가 0이 아닌 이름을 찾아준다.

 

위의 코드는 key의 value가 0인지 아닌지만 확인하면 된다. 

HashMap의 시간복잡도

HashMap은 Dictionary와 같은 역할을 하는 자료구조이다. 

중요한 점은 Hash의 성능을 통해 저장된 Key에 해당하는 Value를 O(1)의 시간복잡도로 검색이 가능하다.

 

HashMap.put(K, V) : O(1)

HashMap.replace(K,V) : 상수기간

자바의 HashMap의 요소에 대한 수정은 생각보다 복잡하다.

replace()와 get()을 통해 접근, 수정해주도록 하자. 말할 필요도 없이 시간복잡도는 상수기간이다.

 

HashMap.containsKey(K), HAshMap.containsValue(V) : O(1), O(n)

Key와 Value를 포함하고 있는지 확인하는 함수이다.

주로 containsKey()를 통해 Key가 있는지 확인하고 없을시 put()해주는 식으로 사용한다.

 

HashMap.keySet() : O(1)

Key를 모아놓은 자료구조를 반환하는 메서드이다. keySet()은 Set<K>를 반환한다.

주로 keySet()을 통해 반환된 Set으로 Map의 요소를 순환하고 싶을 때 사용한다.

 

References

---

• https://www.acmicpc.net/board/view/29052
• http://kwseo.github.io/2015/09/24/time-complexity-about-collections/
• http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html
• https://codeday.me/ko/qa/20190728/1160125.html
• https://velog.io/@wan088/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B3%A0%EB%93%9D%EC%A0%90Kit-1-%ED%95%B4%EC%8B%9C