[프로그래머스] [Hash] 완주하지 못한 선수

문제 : https://programmers.co.kr/learn/courses/30/lessons/42576?language=java

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

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

---

문제 풀이 

 

i) 해시를 사용하지 않는 경우

Hash를 사용하지 않는다면, 배열 두개를 비교하며 배열 내에 존재 여부를 검색하여 loop를 실행하는 방법이 있다.

이 때의 시간복잡도는 O(n^2) 이다.

 

ii) 해시를 사용하는 경우

 

1. 먼저, <참여한 사람, 인원 (동명이인의 경우)를 해시로 만들어주었다.

2. 완주한 사람의 배열 내 요소를 탐색하며 해당하는 key의 value를 -1 씩 계산한다.

3. Hash를 탐색하여 value가 0보다 큰 경우 (완주하지 못한 경우)의 key를 return 한다.

 

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> checkMap = new HashMap<String, Integer>();
		
		//Make hash
		Iterator <Entry <String, Integer>> entries = checkMap.entrySet().iterator();
		for(int i = 0; i < participant.length; i++) {
			if(checkMap.containsKey(participant[i])) {
				checkMap.put(participant[i], checkMap.get(participant[i]) + 1);
			} else {
				checkMap.put(participant[i], 1);
			}
			
		}
		//check completion 
		for(int i = 0; i < completion.length; i++) {
			checkMap.put(completion[i], checkMap.get(completion[i]) - 1);
		}
	
		entries = checkMap.entrySet().iterator();
		while(entries.hasNext()) {
			Map.Entry<String, Integer> entry = entries.next();
			if(entry.getValue() > 0) {
				return entry.getKey();
			}
		}
        return " ";
    }
    
}

---

이론 - Hash

자바에서는 Map이라는 인터페이스가 제공되고, 이 인터페이스를 구현한 클래스로 HashMap, TreeMap, LinkedHashMap 등 3가지가 제공된다. 

HashMap : 해싱 테이블에 데이터 저장

TreeMap : 탐색 트리에데이터 저장

- 정렬된 순서로 방문할 필요가 없다면 HashMap이 약간 더 빠르다.

 

- Hash 객체 선언 

선언은 다른 자바 객체 선언과 같다. 선언 시에는 Map의 key와 value의 type을 지정해주어야 한다. 

Map<keyType, valueType> object = new HashMap<keyType, valueType>();

 

- 데이터 저장 및 수정 - put()

// key에 해당하는 value를 object(Map)에 저장한다.

object.put(key, value);

 

- Map에 저장된 데이터 추출 - get()

// key에 저장된 value를 가져온다.

valueType mapValue = object.get(key);

 

 

- Map에 저장된 데이터 삭제 - remove()

//key의 항목을 삭제한다. 

object.remove(key);

 

- Map 객체 순회하기 (1) : EntrySet 사용

/**

    forEach문을 사용하여 Map 객체를 순회한다.

    순회할 때는 Map.Entry 인터페이스를 사용한다.

**/

for( Map.Entry<keyType, valueType> e : object.entrySet()) {

  // code

}

 

- Map 객체 순회하기 (2) : Iterator 사용

/**

  이번 문제를 풀면서 사용한 방법이다.

  전체 출력 시 사용하면 좋다.

**/

Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()) {
	Map.Entry<Integer, String> entry = entries.next(); 
}

 

가진 기본서의 내용이 부실해서 찾아봤는데 도움된 글이 있어 출처를 남긴다.

https://coding-factory.tistory.com/556

[Java] 자바 HashMap 사용법 & 예제 총정리