[ 해시 Level1 ] 프로그래머스 완주하지 못한 선수 - 자바 Java

https://programmers.co.kr/learn/courses/30/lessons/42576

 

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

 

---

문제를 이해하고 규칙을 찾아보았습니다. 항상 완주자보다 참가자가 적습니다.

그래서 똑같이 정렬을 하고 정렬된 각 위치에 없는 사람을 비교해보아서 결과를 도출해보았습니다.

 

완주하지 못한 선수 자바 코드

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
       
        String answer ="";
        Arrays.sort(participant); //정렬
        Arrays.sort(completion);
        int i;
        for(i=0; i<completion.length; i++){
            if(!completion[i].equals(participant[i])){ //비교 후 다른것을 찾아냅니다.          
                return participant[i];                 
            }
            
        }
        
        return participant[i];
    }
}

 

하지만, 다시 곰곰이 생각해보니.... 문제 유형이 해시(hash)라서 hash를 이용하여 풀어야 공부가 될듯했습니다.

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) {
           hm.put(player, hm.getOrDefault(player, 0) + 1); 
           //getOrDefault : 해당키가 존재하면 키값을 가져오고 아니면 0을 반영합니다.
           //participant은 키값이 존재하지 않으므로 모든 키값에 0 + 1인 1이 대입됩니다.
        }
        
        for (String player : completion) {
           hm.put(player, hm.get(player) - 1);
           //hashmap에 player의 키를 대입하고
           //hm.get(player)값은 completion에서 participant의 키값을 찾습니다. 그리고 -1을 해줍니다.
           //completion에서 participant의 키값이 없다면 해당 키의 키값은 1로 남아있습니다.
        }

        for (String key : hm.keySet()) { //keySet을 이용하여 키만 가져옵니다.
            if (hm.get(key) != 0){ //키를 통해 해당 키값을 가져온 뒤 0이 아닌것을 찾아냅니다.
                answer = key;
            }
        }
        return answer; //결과를 반영합니다.
    }
}

Point

1. getOrDefault() : 해당 키가 존재하면 키값을 가져오고 아니면 기본으로 설정한 값을 반영합니다.

2. keySet() : 키를 가져옵니다.  

   entrySet() : 키와 키값을 가져옵니다.

 

정리

 해당 정리를 해보면

 i) 기존(participant) 키값에 1을 대입하고

 ii) 비교할 값(completion)이랑 같이 키 중에서 해당 키값에 -1을 한 후

 iii) 값을 빼지 못한 값, 즉 0이 아닌 값을 찾습니다.

 

해당 문제의 목적은 두 값을 비교하여 중복이 아닌 값을 찾는 문제였습니다.

 

알고리즘 문제는 먼저 이해를 하고 어떻게 풀어나갈 것인지를 설계하고 복잡하지 않고 간결하게 해결할 수 있는 최선의 해결방법을 찾는 것 같습니다. 또한, 남들의 풀이법이랑 비교해보면서 자신의 부족한 점을 찾는 것도 중요합니다.

 

감사합니다.