[42576] 완주하지 못한 선수

✔ 완주하지 못한 선수

[프로그래머스 42576]

문제 분석하기

해시를 사용해 참가자들을 저장한 후, 완주한 선수들의 이름에 대해 완주 표시를 한 후 완주 표시가 없는 선수를 반환

해시는 값을 삽입하고 검색하는 평균 시간 복잡도가 O(1)

손으로 풀어보기

1. HashMap에 마라톤에 참가한 선수들의 이름과 +1을 저장
   • 동명이인이 존재할 경우를 위해 기존 값에 +1이 됨
   • 동명이인이 존재하지 않는다면 1이 됨
2. HashMap에서 완주한 선수들의 이름에 대해 1에서 -1을 해주며 완주 표시
   • 동명이인이 존재할 경우 한 명의 사람이 완주했다면 2 - 1 = 1이 되게 됨
   • 동명이인이 존재하지 않을 경우 한 명의 사람이 완주했다면 1 - 1 = 0이 되게 됨
3. HashMap에 완주 표시인 0이 아닌 선수 이름 반환

슈도코드 작성하기

participant(마라톤에 참여한 선수들의 이름이 담긴 배열)
completion(완주한 선수들의 이름이 담긴 배열)
map(마라톤에 참여한 선수들의 이름과 완주 여부가 담긴 hashMap)
map에 participant, +1 저장하기
map에서 completion, -1 갱신하기
map에서 0이 아닌 선수 찾아서 반환하기

코드 구현하기

/**
 * 42576) 완주하지_못한_선수
 */
public class K002_42576 {
    // participant(마라톤에 참여한 선수들의 이름이 담긴 배열)
    // completion(완주한 선수들의 이름이 담긴 배열)
    public String solution(String[] participant, String[] completion) {
        // map(마라톤에 참여한 선수들의 이름과 완주 여부가 담긴 hashMap)
        Map<String, Integer> map = new HashMap<>();
        // map에 participant, +1 저장하기
        for (String player : participant) {
            map.put(player, map.getOrDefault(player, 0) + 1);
        }
        // map에서 completion, -1 갱신하기
        for (String finisher : completion) {
            map.put(finisher, map.get(finisher) - 1);
        }
        // map에서 0이 아닌 선수 찾아서 반환하기
        String answer = "";
        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                answer = key;
            }
        }
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K002_42576 solution = new K002_42576();

        String[] participant = { "leo", "kiki", "eden" };
        String[] completion = { "eden", "kiki" };

        String result = solution.solution(participant, completion);

        System.out.println(result);
    }
}