[JAVA] 프로그래머스 - 완주하지 못한 선수 LV1

문제 이해 및 제한 사항

프로그래머스의 해시 문제, 완주하지 못한 선수 LV1

https://programmers.co.kr/learn/courses/30/lessons/42576?language=java 

코딩테스트 연습 - 완주하지 못한 선수

입출력 예시

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

본 문제는 N명이 마라톤 경기에 참여하였지만 N-1명만 통과하고 통과되지 못한 1명을 찾는 문제입니다.

해쉬로 푸는 문제이니 해쉬로 풀어봐야겠습니다. 해쉬 외 방법으로의 풀이는 아래 링크를 참고하면 좋을 듯합니다.

 

문제 해결 순서

1. 해쉬의 KEY와 VALUE에 어떤 값을 넣어서 문제를 해결할지 고민한다.     가장 어려운 부분

• INPUT으로 참가자(Participant)와 통과자(Completion) 배열이 들어온다.
• 배열을 순환하면서 해쉬의 key에 참가자 이름을 넣고, value에 참가한 자(key)에 대해  +1을 해준다. (동명이인을 고려)

2. 통과자 배열을 돌면서 해쉬의 key에 있으면 value를 -1한다.

3. value가 0이 아닌 참가자는 통과자 배열에 없는 참가자일 것이므로 완주하지 못한 선수로 리턴한다.

 

코드

# 풀이 1. 4번째 문제 해결을 Iterator를 이용해서 푼다.  (더 높은 속도를 보여준다.)

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Iterator;

public class 해쉬_완주하지못한선수 {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> map = new HashMap<>();
        Arrays.sort(participant);
        Arrays.sort(completion);

        // hashMap에 추가
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1); // p가 key에 있으면 value를 가져옴. 없으면 디폴트 0
        }
        // 통과된 선수들 제거
        for (String c : completion) {
            map.put(c, map.get(c)-1);
        }
        // 순환하면서 0인 선수 return
        // Iterator가 더 속도높음
        Iterator<String> keys = map.keySet().iterator();
        while (keys.hasNext()) {
            String key = keys.next();
            if (map.get(key) != 0) {
                answer = key;
                break;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        해쉬_완주하지못한선수 k = new 해쉬_완주하지못한선수();

        String[] part = {"marina", "josipa", "nikola", "vinko", "filipa"};
        String[] comp = {"josipa", "filipa", "marina", "nikola"};

        String answer = k.solution(part, comp);
        System.out.println(answer);
    }
}

 

 

# 풀이 2. 4번째 문제 해결을 해쉬의 keySet을 이용한 반복문으로 푼다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 해쉬_완주하지못한선수 {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> map = new HashMap<>();
        Arrays.sort(participant);
        Arrays.sort(completion);

        // hashMap에 추가
        for (String p : participant) {
            map.put(p, map.getOrDefault(p, 0) + 1); // p가 key에 있으면 value를 가져옴. 없으면 디폴트 0
        }
        // 통과된 선수들 제거
        for (String c : completion) {
            map.put(c, map.get(c)-1);
        }
        // 순환하면서 0인 선수 return
        for (String key : map.keySet()) {
            if (map.get(key) != 0) {
                answer = key;
                break;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
		// 생략
    }
}

 

 

참고글 : 자세한 설명이 나와있어 좋은 글입니다. 
해쉬 순회 방법 참고글
위 코드의 깃허브

해쉬_완주하지못한선수 · BananMoon/algorithm_study@b1a2542