프로그래머스_해시_완주하지 못한 선수 (Java)

문제 풀이에 대한 오류 지적 및 개선 방향 제시는 항상 환영합니다.

알고리즘 문제를 엄청 잘 풀고 막 문제 보자마자 아 이거네 쉽네 ㅎㅎ 이렇게 푸는 입장이 아니라서

그 어떤 문제에 대한 비판 지적 방향제시는 언제나 감사하게 받겠습니다. 

 

문제 설명

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

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

 

제한사항

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

입출력 예

 

participant	completion	return
[leo, kiki, eden]	[eden, kiki]	leo
[marina, josipa, nikola, vinko, filipa]	[josipa, filipa, marina, nikola]	vinko
[mislav, stanko, mislav, ana]	[stanko, ana, mislav]	mislav

 

입출력 예 설명

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

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

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

 

해결 방법

처음 시도했을 때는 ArrayList 나 Queue를 사용해서 풀었다가 '선수의 수는 1명 이상 100,000명 이하'의
조건으로 해시 맵을 이용 하여 다시 풀게 되었다. 동명이인의 조건이 같이 있으니 아무래도 최악의 경우
10만 vs 1의 결과를 가져올 수 있을 거라 생각했다.

풀이 방법은 굉장히 단순했다. Key값으로 String을, Value로 Integer를 갖는 해시 맵을 새로 생성하였고
participant 배열을 처음부터 끝까지 모두 해시 맵에 저장하도록 했다.

단순히 저장한 것은 아니다. 동명이인의 경우를 생각해야 했기 때문에 HashMap.containsKey(Key)를
사용하여 저장하였다. HashMap.containsKey(Key)는 true or false를 리턴하는데, 함수의 파라미터 값을
해시 맵이 키로 갖고 있다면 true, 아니면 false를 반환한다. 이것을 이용하여 false 일 경우 단순하게
해시 맵에 저장, true 일 경우 key에 대한 value를 + 1 하는 방식으로 저장하였다.

이제 완주한 선수를 체크하여 완주에 실패한 선수들을 찾아내야 한다. completion 배열 내의 String 값을
Key 값으로 사용하여 반환된 value 가 1 일 경우 해시 맵을 제거하는 remove 함수를 사용하였고,
아닌 경우 value에 -1을 해주어 replace를 해주었다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 의 조건을 생각하여 Iterator를
사용하여 playerMap의 Key를 저장해 주었고, itr.next()를 반환하여 문제를 해결하였다.

 

Solution.Java

 

import java.util.HashMap;
import java.util.Iterator;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        answer = RetirePlayer(participant, completion);
        return answer;
    }
    private String RetirePlayer(String[] participant, String[] completion){
        String retire;
        HashMap<String, Integer> playerMap = new HashMap<>();
        for(String player : participant){
            if(!playerMap.containsKey(player)){
                playerMap.put(player, 1);
            }
            else{
                playerMap.replace(player, playerMap.get(player) + 1);
            }
        }
        for(String player : completion){
            if(playerMap.get(player) == 1){
                playerMap.remove(player);
            }
            else{
                playerMap.replace(player, playerMap.get(player) - 1);
            }
        }
        Iterator<String> itr = playerMap.keySet().iterator();
        retire = itr.next();
        return retire;
    }
}

 

Github : https://github.com/hwk0911/Junit-TDD

hwk0911/Junit-TDD