[프로그래머스,Level 1] 완주하지 못한 선수(JAVA 구현)

- 첫 풀이 및 정답풀이

이 문제의 경우 주어지는 두 가지 배열을 적절히 이용하면 풀 수 있다고 생각이 들었고, 문제에서 제시하는 자료구조인 해시를 이용해 풀어보고자 하였다. 해시를 많이 사용해보지 않아 공부하는 차원에서 처음부터 다른 분들의 풀이를 보고 풀어보았다.

이 문제의 핵심은 참여자 명단과 완주 명단이 주어지며, 두 명단 사이 크기 차이는 1이라는 점이다. 즉, 완주하지 못한 한 명을 찾아내는 것이 핵심이라 할 수 있다.

import java.util.*;
import java.util.Map.Entry;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        // 1. 해시맵 사용.
        HashMap<String,Integer> map = new HashMap<>();
        
        // 2. 해시맵의 요소로 참여자 등록.
        for(String str : participant){
            map.put(str,map.getOrDefault(str,0)+1);        
        }
        
        // 3. 해시맵의 요소에서 완주자 확인.
        for(String str : completion){
            map.put(str,map.get(str)-1);          
        }
        
        // 4. 완주하지 못한 사람을 반환.
        for(Entry<String,Integer> entry : map.entrySet()){
            if(entry.getValue() > 0){          
                answer = entry.getKey();
                break;
            }
        }
        
        return answer;
    }
}

간단하게 해시 맵은 ky-value 형태로 데이터를 관리하며, 데이터의 저장과 검색이 매우 빠른 자료구조라고 한다. 이때 key값은 중복될 수 없지만, value 값은 중복이 가능하다. 위 문제에서 사용한 해시 맵의 경우 key가 String 타입, value는 Integer 타입을 사용한다.

해시맵에 데이터의 삽입은 put(key, value) 메서드를 이용해 가능하며, get(key)메소드로 value값을 가져올 수 있다. 위 문제에서는 key에는 참가자의 명단, value에는 map.getOrDefault() 메서드를 사용하였다. 또한, 기존의 key에 새로운 value를 삽입하면 해당 value는 갱신된다.

여기서 getOrDefault(key,defaultValue)메소드는 특정 key에 대한 value가 존재한다면, 해당 value를 사용하고 존재하지 않는다면 defaultValue를 사용한다.

완성된 해시맵을 탐색하는 방법으로는 대표적으로 keySet() 메서드와 entrySet()을 이용하는 방법이 있는데, keySet()의 경우는 해시 맵에 저장된 key값을 참조하는 방법이고, entrySet()은 특정 원소의 key와 value를 Entry객체로 묶어 참조하는 방법이다.

위 코드의 동작이해는 아래와 같다.

1. 비어있는 해시맵에 map.put(str, getOrDefault(str,0)+1을 이용해 데이터를 삽입한다. 이 코드가 의미하는 것은 참가자 명단에서 동명이인이 존재할 수 있기 때문에, 삽입되지 않은 사람이면, default값인 0에 +1을 통해 해당 이름의 참가자 수를 늘리고, 이미 삽입되어있던 사람이라면 동명이인이기 때문에 기존의 1인 value에 +1을 수행한다. 예제 1번이 이를 수행한 해시맵은 아래와 같다.

participant	key	value
eden	eden	1(0+1)
kiki	kiki	1(0+1)
leo	leo	1(0+1)

참가자 모두 처음 등록하는 참가자이므로 default인 0+1로 value는 1이 된다.

2. 두 번째 map.put(str,map.get(str) -1)을 이용해 key값인 완주자들의 value 값을 제거해준다. 만약, 동명이인이라 하더라도, 2명 중 한 명이 완주하지 못한 것은 동명이인이기 때문에 상관이 없게 된다.

participant	key	value
eden	eden	0(1-1)
kiki	kiki	0(1-1)
leo	leo	1(완주x)

3. map.entrySet()을 이용해 해시맵의 원소들을 entry객체로 가져온 뒤, value가 0 이상인 사람의 key값을 반환한다.

+) 해시맵의 탐색에서 keySet()과 entrySet()의 차이는 value값의 참조 여부에 따라 성능이 다르다고 한다. keySet()의 경우 모든 원소의 key값만을 가져오는데, 이 key를 이용해 map.get(key)를 수행한다면 value를 찾기 위해 해시 맵을 다시 탐색하기 때문에 비효율적이라고 한다. 그러나 entrySet()의 경우는 원소들의 key, value를 객체 형태로 받아오기 때문에 key가 필요하면 getKey(), value가 필요하면 getValue()를 사용하면 된다고 한다.

저작자표시

- 첫 풀이 및 정답풀이

티스토리툴바