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

안녕하세요😎 백엔드 개발자 제임스입니다 :)

프로젝트가 끝나고, 오랜만에 문제 풀이 글을 올립니다. 이번은 백준이 아닌, 프로그래머스를 도전하게 되었는데요. 어느정도에 난이도일지 몰라서 Level1부터 시작하고 있습니다. 하지만 오랜만이여서 그런지 쉽지 않네요 😂꾸준함에 중요성을 뼈저리게 느끼게 되었습니다.

---

(Level1 / 42576) 완주하지 못한 선수

---

1) Problem

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

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

2) 제한사항

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

3) 입출력 예

---

풀이

---

해당 문제는 HashMap으로 접근하면 좋습니다. 저는 처음 HashSet으로 접근했는데요. 반복문이 많이 들거가게 되면서 시간초과가 발생했습니다. 또한 동명이인이 있다는 조건으로 풀이가 적절하지 못했습니다.

HashMap으로 접근한다면, 

완주한 사람의 이름과 횟수를 카운팅하여 저장하도록 하도록 합니다. 최종적으로 완주하지 못한 사람까지 체크할 수 있게 됩니다.

import java.util.HashMap;

public class 완주하지_못한_선수 {

    public String solution(String[] participant, String[] completion) {
        String answer = "";

        HashMap<String, Integer> map = new HashMap<>();

        for (String name : participant) {
            map.put(name, map.getOrDefault(name, 0) + 1);
        }

        for (String name : completion) {
            map.put(name, map.get(name) - 1);
        }

        for (String key : map.keySet()) {
            if (map.get(key) > 0) {
                answer = key;
                break;
            }
        }
        return answer;
    }
}

 

 

위 코드를 보다시피 HashMap을 사용한 것을 알 수 있습니다. 해당 문제를 처음 접근했을 때 어떻게 풀어야 할지 난감할 수 있습니다. 그 이유는 배열 participant와 배열 completion을 보았을 때 정렬 상태가 아니기 때문입니다. 즉, 단순하게 Index를 활용하는 문제가 아니라는 의미입니다. 따라서 해당 문제는 정렬과 무관한 Hash를 활용하게 됩니다.

Hash를 활용하는 컬렉션으로 HashSet과 HashMap이 있습니다. Hash는 기본적으로 중복을 허용하지 않습니다. 여기서 또 한번 고민에 빠질 수 있습니다. 해당 문제의 조건을 보면 동명이인이 있을 수 있다는 내용이 있습니다. 즉, 중복인 경우도 고려해야 한다는 것이죠.

단순히 HashSet을 사용한다면, 동명이인 케이스를 처리할 수 없게 됩니다. 따라서 HashMap을 활용해야 하는데요.

HashMap은 <key, value> 형태로 데이터를 저장합니다. 그래서 우리는 key에 마라톤 참석자를 문자열로 저장하고, value에는 Integer로 참석자 수를 저장합니다. 중복되는 경우에는 기존의 값에 +1이 됩니다. 반대로 완주하는 선수[completion 배열]에 해당하는 경우에는 -1을 시켜줍니다. 최종적으로는 value가 1인 key 가 남을테고, 이는 곧 우리가 찾는 완주하지 못한 선수가 됩니다.

---

HashMap.getOrDefault(Object key, Object defaultValue)

1) Java 8에서 추가된 Collection API 메서드입니다.
2) 찾는 key가 존재한다면, key의 value를 반환하고, 없을 경우(null)에는 default 값을 반환합니다.
3) 매개변수 중 defaultValue는 지정된 키로 매핑된 값이 없을 때(null) 반환되는 key 값입니다.