import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
HashMap<String,Integer> map = new HashMap<>();
for(String player : participant) map.put(player, map.getOrDefault(player,0)+1);
for(String player : completion) map.put(player, map.get(player)-1);
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if(entry.getValue() !=0){
answer = entry.getKey();
break;
}
}
return answer;
}
}
완주하지 못한 선수
문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다.
문제 접근 방식 (문제 단순화 하기)
늘 그렇듯,문제를 간단하게 만들어보는 것이 1단계이다.
Participant 배열로는 N명의 참가자의 이름이 들어있고, Completion 배열에는 N-1명의 완주자들이 있다.
그 한 명을 찾으면 되는 아주 간단한 문제이다.
간단한 예시를 하나 만들어서 문제를 해결할 알고리즘을 고민해보면 생각보다 쉬운 해결책이 나온다.
위 예시에서는 B가 답이라는 것이 너무 쉬워서 알고리즘을 유추하기 어려울 수 있는데, 결론은좌우를 비교해서 없는 것 하나만 찾으면 된다.
사람 눈으로 보고 찾는 건 너무 자연스럽지만, 이걸 프로그램으로 짜서 어떻게 컴퓨터에게 전달할 수 있을까?
해결책 1 : Sorting 한 뒤에 Loop을 통해 1:1 비교를 하고, 서로 다른 항목이 나온 사람이 완주하지 못한 사람이다.
해결책 2 : 그래도 명색이 해시 문제인데... 해시를 사용하는 방법이 있다.
풀이1
public String solution(String[] participant, String[] completion) {
Arrays.sort(participant); //이름 순으로 정렬
Arrays.sort(completion); // 이름 순으로 정렬
//참가자와 완주자의 이름을 비교해서 다르면, 완주를 못한 사람이기 때문에 그 값을 return
for(int i=0; i<completion.length; i++){
if(!participant[i].equals(completion[i])){
return participant[i];
}
}
//완주자를 끝까지 비교했는데, 다른 이름이 없다면 참가자의 마지막사람이 미완주자
return participant[participant.length-1];
}
참가자와 완주자의 비교를 위해, 우선 이름 순으로 두 배열 모두 정렬한다. 두 배열의 이름을 비교하여, 이름이 같으면 완주자, 다르면 미완주자로 판단한다. 만약 완주자의 끝까지 비교했을 때, 다른 이름이 없다면, 참가자의 마지막 사람이 미완주자이다.
풀이2 - Hash 사용
public String solution(String[] participant, String[] completion) {
String answer = "";
//hasp map 생성
HashMap<String, Integer> map = new HashMap<>();
for (String player : participant)
//getOrDefualt : player의 값을 가진 key를 가져와서 없으면 0을 가져와서 1을 더하고,
있으면 그 값을 가져와서 1을 더한다.
map.put(player, map.getOrDefault(player, 0) + 1);
//Hash map에서 완주한 사람 빼기
for (String player : completion)
//기존의 있던 값을 가져와서 -1 한다
map.put(player, map.get(player) - 1);
/*for(string key : map.keySet()){
if(map.get(key) != 0){
answer = key;
break;
}*/
//위의 코드 대신 아래 코드도 사용가능. EntrySet이 반복문을 사용할때 속도가 더 빠름.
Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();
while(iter.hasNext()){
Map.Entry<String, Integer> entry = iter.next();
if (entry.getValue() != 0){
answer = entry.getKey();
break;
}
}
return answer;
}
Hash를 사용해서 문제를 푸는 방법. Hash map을 만들어서 key를 선수이름, value를 선수의 수로 설정한다. completion에서 가져온 선수를 map에서 빼면, 완주를 한 선수는 0이 되고, 완주를 못한 선수는 1로 남아있다. value가 1인 선수가 완주를 못한 선수.
