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

완주하지 못한 선수

프로그래머스 사이트 코딩 테스트 고득점 Kit 메뉴에 해시 카테고리에 Level 1문제이다.

해시맵 자료구조를 사용하면 더 효율적으로 해결할 수 있는 문제가 존재한다. 

해시맵 자료구조는 key-value쌍으로 저장하며 검색과 입력이 O(1)인 장점이 있는 자료구조이다.

 

문제의 요구사항은 마라톤에 참여한 선수들의 이름이 담긴 배열과 완주한 선수의 이름이 담긴 배열이 주어지고 완주하지 못한 선수의 이름을 리턴하는 것이다.

테스트 케이스마다 완주하지 못한 선수는 항상 1명이며 또한 동명이인이 있을 수 있으니 주의하여야 한다.

문제 해결의 핵심 아이디어

문자열을 비교해야하며 동명이인이 존재하기 때문에 이 또한 카운트를 해야한다. 

 

1. 해시맵 자료구조에 참석한 선수의 이름과 인원 수를(동명이인이 있을 수 있으니) 입력

2. 위 해시맵에 완주자 이름을 검색하여 인원 수를 차감

3. 해시맵에 완주자 이름으로 검색하여 인원 수가 차감되지 않은 값을 반환

 

해시맵을 사용하는 이유는 입력과 검색이 빠르기 때문이다.

문제 해결 코드

import java.util.HashMap;
import java.util.Map.Entry;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer ="";
        HashMap<String, Integer> hashMap = new HashMap<>();

	//hashMap에 모든 참가 선수 입력, 동명이인이 있을 경우 value = value + 1
        for (String s : participant) {
            if (hashMap.containsKey(s)){
                hashMap.put(s, hashMap.get(s) + 1);
                continue;
            }
        	hashMap.put(s, 1);
        }

	//hashMap에 완주 선수를 검색하여 value - 1씩 차감
        for (String s : completion) {
            if (hashMap.containsKey(s)){
                hashMap.put(s, hashMap.get(s) - 1);
            }
        }
        
	// hashMap을 전부 탐색하여 value 1을 찾고 이에 대한 key값을 반환
        for (Entry<String, Integer> s : hashMap.entrySet()){
            if (s.getValue() == 1){
                answer = s.getKey();
                break;
            }
        }
        
    	return answer;    
    }
}

배운 점

getOrDefault()

Java 8에 추가된 Map 인터페이스에 정의된 getOrDefault() 메서드를 사용하면 Map 인터페이스를 구현한 자료구조를 사용하여 값을 가져올때 매핑된 값이 없으면 기본값을 정할 수 있다.

get()만 사용하는 경우

//getOrDefault를 사용하지 않을 경우에는 get의 값이 null값이 반환될 수 있기 때문에
//항상 key의 존재를 확인하여야 한다.
for (String s : participant) {
    if (hashMap.containsKey(s)){
        hashMap.put(s, hashMap.get(s) + 1);
        continue;
    }
    hashMap.put(s, 1);
}

getOrDefault()를 사용하는 경우

//값이 없을 경우 0을 반환하기 때문에 null 체크를 하지 않아도 된다.
for (String s : participant) {
    hashMap.put(s, hashMap.getOrDefault(s, 0) + 1);
}

entrySet() vs keySet() 속도 차이

모든 key-value쌍을 순회할 때 keySet()을 사용하는 경우 모든 key에 대해 일일히 get() 메서드를 호출하고 이 메서드는 hash() 메서드를 사용하기 때문에 entrySet에 비해 속도면에서 비효율적이다.

그에 반해 entrySet은 value까지 Set에 담아주기 때문에 따로 get메서드를 일일히 호출하지 않는다.

 

결론적은 모든 key-value쌍을 순회할때에는 entrySet()을 권장한다.

 

아래는 문법차이를 보여준다.

 

entrySet()을 사용하는 경우

//entrySet 사용
for (Entry<String, Integer> es : hashMap.entrySet()) {
    if (es.getValue() == 1) {
        answer = es.getKey();
        break;
    }
}

keySet()을 사용하는 경우

//keySet 사용
for (String s : hashMap.keySet()){
    if (hashMap.get(s) == 1){
        answer = s;
        break;
    }
}