[프로그래머스] (Java) 코딩테스트 완주하지 못한선수 문제풀이 🚴‍♂️ (해시) - map.getOrDefault()

 

 

❤️ 문제설명

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

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

 

💛 제한사항

- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

- completion의 길이는 participant의 길이보다 1 작습니다.

- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

- 참가자 중에는 동명이인이 있을 수 있습니다.

 

💚 입출력 예

​예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

💜 풀이

 

[LOOP 방식]

 

- 두 개의 배열 : participant N명의 참가자 이름, completion N-1명의 완주자들

- 두 배열을 정렬 한 후 for문을 돌려서 비교했을 때 일치하지 않는 값을 찾으면 된다고 생각했다.

- 배열을 0번 인덱스부터 순차적으로 돌리면서 문자열을 비교하는데,  participant[i]값고 completion[i]값이 일치하지 않는 부분에서 참가자를 return 해 주면 된다.

- 문자열 부정 비교는 !비교대상1.equals(비교대상2)

- 배열을 모두 순회 했는데도 일치하는 값이 없다면 participant의 마지막 인덱스에 담긴 사람이 미완주자이다.

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // 1. 배열 정렬
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        // 2. for문 돌려서 배열 비교
        int i;
        for (i = 0; i < completion.length; i++) {
            if (!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        // 3. 마지막 주자가 완주하지 못한 경우
        return participant[i];
    }
}

 

 

[HashMap 방식]

하지만 이 문제의 카테고리는 해시.

명색이 해시문제인 만큼 해시로 푸는 코드도 짜 볼 수 있다.

 

HashMap은 시간복잡도 면에서 Loop보다 훨씬 유리하고, 대량의 데이터 탐색에 적합하다.

키,값 쌍을 갖기 때문에 Loop를 순회하지 않고 키를 통해 데이터를 검색하고 저장함.

Loop의 시간복잡도는 O(n), 해시는 O(1)로 데이터가 많을 수록 접근 속도 측면에서 유리하다.

 

- 참가자 배열로 해시맵 구성 : 참가자의 이름을 키(key)로, 이름이 등장한 빈도수(count)를 값으로 매핑

- 완주자 배열 순회하면서 해시맵에서 1값을 감소

- 값이 0이 아닌 키가 완주하지 못한 참가자의 이름

 

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 1. 참가자 배열로 해시맵을 구성
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1);  // 참가자 이름을 키로, 카운트를 값으로 저장
        }
        
        // 2. 완주자 배열을 순회하면서 해시맵에서 값을 감소
        for (String c : completion) {
            map.put(c, map.get(c) - 1);  // 완주자에 해당하는 이름의 값을 1씩 감소
        }
        
        // 3. 값이 0이 아닌 키가 완주하지 못한 참가자
        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                return key;  // 값이 0이 아닌 참가자 이름을 반환
            }
        }
        
        return "";  // 조건에 맞는 참가자를 찾지 못할 경우(일반적으로는 발생하지 않음)
    }
}

 

map이라는 이름의 해시맵 만들기

 

 map.put(p, map.getOrDefault(p, 0) + 1); 

put 메서드로 해시맵에 새로운 키-값 쌍을 추가 

 

participant 배열의 각 이름(p)을 키로 추가하고, 해당 이름이 해시맵에 없다면 초기값으로 0을 설정. 있으면 1씩 더해주기

각 참가자 이름이 키, 이름 출현 빈도가 값이 됨

 

 map.put(c, map.get(c) - 1); 

해시맵에서 완주자에 해당하는 이름의 값을 1씩 감소

 

map.keySet()으로 해시맵에 있는 모든 키값에 대해 아래 작업을 반복하는데

현재 키에 대한 값을 가져와서 그 값이 0이 아닌지를 체크한다.

여기서 값은 그 참가자가 몇 번 참가했는지를 나타내는데, 만약 값이 0이라면 해당 참가자는 완주했음을 의미

반대로, 값이 0이 아니라면 그 참가자는 완주하지 못한 것이기 때문에 값이 0이 아닌 키가 미완주자의 이름이 된다.