[Java] 프로그래머스 : 완주하지 못한 선수 (feat. HashMap)

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

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

입력

• participant : 마라톤에 참여한 선수들의 이름이 담긴 String 배열
• completion : 완주한 선수들의 이름이 담긴 String 배열

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

출력

완주하지 못한 선수의 이름을 return

---

풀이

처음엔 hash문제인지 모르고 배열 그대로 풀었다.

participant와 completion을 정렬한 뒤 앞에서부터 차례로 문자열을 비교해 다른 이름이 나오면 return했다.

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        for(int i=0;i<completion.length;i++){
            if(participant[i].equals(completion[i])==false){
                return participant[i];
            }
        }        
        return participant[participant.length-1];
    }
}

정렬(Sort)을 사용할 경우 코드는 간결하지만, 시간복잡도가 O(n)(단순탐색) => O(nLogN) ~ O(n^2)로 늘어난 단점이 있다.

 

HashMap 사용

해시(Hash)는 키 값이 배열 인덱스로 변환되고, 그 배열 인덱스를 사용해서 검색, 삽입, 삭제 등이 빠르며 중복 제거에 유용하다. 하지만 순서 있는 배열에는 어울리지 않으며 해시 함수의 의존도가 높다.

해시맵의 사용법을 잘 몰라서 정리하면서 풀이를 적었다.

선언과 값 추가

HashMap<Integer,String> map = new HashMap<>(); //new에서 타입 파라미터 생략가능
map.put(key,value); //값 추가

선언 시 HashMap에 설정해준 타입과 같은 key와 value값을 넣어야하며 만약 입력되는 키 값이 HashMap 내부에 존재한다면 기존의 값은 새로 입력되는 값으로 대치된다.

하지만 참가자 중 동명이인이 있을 수 있기 때문에 (제한사항 4) 중복처리를 해줘야 한다. 그 방법은 다음과 같다.

getOrDefault(Object key, V DefaultValue)

찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드

• key : 값을 가져와야하는 요소의 키
• deaultVaule : 지정된 키로 매핑된 값이 없는 경우 반환되어야하는 기본값

위에서 설명했듯이, HashMap의 경우 동일 키 값을 추가할 경우 value값이 덮어쓰기가 된다. 따라서 기존 key값의 value를 계속 사용하고 싶을 경우, 즉 참가자 동명이인의 중복처리를 해주고 싶을 경우에 getOrDefault 메서드를 사용한다.

for(String player : participant) map.put(player, map.getOrDefault(player,0)+1);

참가자를 map에 put 해줄 때, map.getOrDefault(player,0) 을 사용해서 이미 map에 있는 참가자인지 확인한다.

1. 아직 등록되지 않은 참가자라면 default 값인 0이 반환되어 최종적으로 map.put(player, 1)가 실행된다.
2. 만약 이미 등록되있는 참가자라면(동명이인) 해당 참가자에 해당하는 value값인 1이 리턴되어 최종적으로 map.put(player, 2)가 실행된다.

완주자의 경우에도 동일한 map을 이용해서 처리해 줄 수 있다. 완주자(key)에 해당하는 value값에 -1을 해주는 것이다.

for(String player : completion) map.put(player, map.get(player)-1);

 

HashMap 전체 값 출력

map에 값을 전체 출력하기 위해서는 entrySet(), keySet() 메소드를 사용한다.
entrySet()은 key와 value의 값이 모두 필요한 경우에 사용하고, keySet()는 key값만 필요한 경우 사용한다.

entrySet()의 getKey()와 getValue()는 현재 차례의 entry 속성 값을 바로 가져오는 반면, keySet()의 get()은 HashMap을 search 해야하므로 내부에서 hashcode(), equals()등을 실행하기 때문에 효율성이 떨어진다.

따라서 entrySet()의 사용을 권장한다.

풀이 코드

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String,Integer> map = new HashMap<>();
        
        for(String player : participant) map.put(player, map.getOrDefault(player,0)+1);
        for(String player : completion) map.put(player, map.get(player)-1);
        
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if(entry.getValue() !=0){
                answer = entry.getKey();
                break;
            }
        }
        
        return answer;
    }
}

 

+ 참고

[JAVA] Map - getOrDefault 이란? 사용법 및 예제

[Java] Map 전체 출력(entrySet, keySet, Iterator)