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

#프로그래머스>해시>완주하지 못한 선수

 

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

---

풀이 : completion 배열에는 없고 participant 배열에는 있는 사람을 찾으면 된다.

 

 

1)sort()사용

- participant와 completion를 정렬한 후 => Arrays.sort(); 이용

- 같은 index의 participant와 completion값이 다른 것이 완주하지 못한 선수

 

 

[첫오답풀이]

participant가 1명 더 많기 때문에, 답이 마지막 index일 경우 completion의 IndexOutOfBoundsException 발생 

import java.util.Arrays;
class Solution {
    public String solution(String[] participant, String[] completion) {
        int i = 0;
        String answer = "";
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        while(true){   
            if(!participant[i].equals(completion[i])){
                answer = participant[i];     
                break;
            }else{
                i++;
            }
        } 
        return answer;
    }
}

      

 

 

[정답]

completion의 length만큼 비교 후, answer 가 null 일 때 마지막 index의 participant가 정답

import java.util.Arrays;
class Solution {
    public String solution(String[] participant, String[] completion) {
        int i = 0;
        String answer = "";
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        while(i<completion.length){
            if(!participant[i].equals(completion[i])){
                answer = participant[i];     
                break;
            }else{
                i++;
            }
        }
        if("".equals(answer)){
            answer = participant[i];    
        }
        return answer;
    }
}
​

 

 

 

위 문제풀이가 직관적이지만 해당 문제 카테고리가 Hash이기도 하고,

다량의 비교가 필요한 경우 Hash가 효율적이므로 추후 Hash를 사용해서 풀어보기도 필요***

 

2)Hash사용

- 컬렉션의 HashMap을 사용

=> HashMap은 Key값을 해싱해 찾기 좋게 분류해둔다.

    여기서는 배열 안의 문자열을 해싱해야하니 Key에 문자열을 넣으면 자동으로 해싱돼서 저장된다는 의미이다.

- getOrDefault(key, defaultValue) : map에서 찾는 Key의 값 반환, 없다면 defaultValue 를 리턴함

 

Ex)

String[] arr1 = {"mislav", "stanko", "mislav", "ana"};
String[] arr2 = {"stanko", "ana", "mislav"};

Map<String, Integer> map = new HashMap<String, Integer>();
for(String a : arr1) map.put(a, map.getOrDefault(a, 0) + 1);
System.out.println(map);
// 이름을 Key, 해당 이름의 학생 수를 value 에 넣는다.
// {ana=1, mislav=2, stanko=1}

 

 

[정답]

 

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        //선수 셋팅
        for(String str : participant){
            map.put(str, (map.getOrDefault(str, 0)) +1);
        }
        
        //완주자 가감
        for(String str : completion){
            map.put(str, map.get(str)-1);
        }
        
        //가감되지 않은 선수(완주하지 못한 선수) return
        for(String str : map.keySet()){
            if(map.get(str) > 0){
                return str;
            }
        }
        
        return answer;
    }
}