프로그래머스(JAVA) - Hash (완주하지 못한 선수)

 

문제정리

참여한 선수들의 이름이 담긴 배열 participant, 완주한 선수들의 이름이 담긴 배열 completion
완주하지 못한 선수이름은 return
이름은 알파벳 소문자로 이루어져 있으며, 참가자 중에는 동명이인 존재

 

이 문제의 포인트 중 하나는 completion의 길이는 participant의 길이보다 1 작다 라는 부분인 것 같다. 그러면 무조건 완주하지 못한 선수가 1명이라는 뜻이기에 그걸 처음에 잡아내지 못함

처음 작성한 코드

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);

        int i = 0;
        for(i=0;i<completion.length;i++)
            if(!participant[i].equals(completion[i]))
                break;

        return participant[i];
    }
}

 

두 배열을 전부 오름차순으로 정렬해주어 이름이 동일한 위치 오게끔 해주었고, 각 위치에 동일한 이름이 들어있지 않을 시 바로 break 하여 반복문을 종료하고 해당 위치에 있는 참가자를 반환시켰다.

시간은

 

HashMap 구현

import java.util.HashMap;

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

        // 참가자 명단을 HashMap에 저장 (이름별 개수 카운트)
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1);
        }

        // 완주자 명단을 확인하면서 참가자 명단에서 제거
        for (String c : completion) {
            map.put(c, map.get(c) - 1);
        }

        // value가 1인 참가자가 완주하지 못한 사람
        for (String key : map.keySet()) {
            if (map.get(key) > 0) {
                return key;
            }
        }

        return ""; // 정상적으로 동작하면 여기에 도달하지 않음
    }
}

 

HashMap은 Key-Value의 Pair를 관리하는 클래스로,
HashMap<String,Integer>로 지정하면 Key는 String, Value는 Integer 형태로 정의하는 것이다.

map.getOrDefault(p, 0) -> HashMap에 값이 있으면 기존 값 반환하고, 없으면 기본값 0을 반환

keySet -> HashMap 에 저장된 모든 키 값들을 가져오는 메서드

 

---

 

이전 코드와 비교했을때 HashMap을 사용하면 정렬 없이 더 빠르게 해결 가능하며, 더 많은 참가자가 있을 경우에도 빠르게 찾을 수 있음.