[프로그래머스] 코딩테스트 연습 > 해시 > 완주하지 못한 선수

문제 설명

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

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

제한사항

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

입출력 예participantcompletionreturn

["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.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        int test;
        
        for(int i=0;i<participant.length;i++){
            test = Arrays.asList(completion).indexOf(participant[i]);
            if(test!=-1){
                completion[test]=null;
            }else{
                answer=participant[i];
                break;
            }
        }
        
        return answer;
    }
}

 하나 하나 대입해서 확인하는 것

하지만 이렇게 하는 것에는 치명적인 단점이 존재한다.

시간 초과............ 하나하나 대입하고 존재하는지 확인하고 삭제하는 과정을 반복하는 사이 시간초과로 이미 탈락,,,,,,,,

 

시간초과가 된 이유를 생각해보면,

participant 배열의 길이만큼 for loop를 반복하는 동안 계속

String 배열인 completion 을 Arrays.asList()를 통해서 List로 만들어 준 다음 completion에서 participant[i]의 주소를 찾는 과정을 반복하다보니 생긴 문제라고 생각된다.

 

아마 아예 Arrays.asList(completion)를 ArrayList 타입의 새로운 변수로 만들어서 저장해두고 했으면 시간은 좀 줄었을 수도 있다.

하지만 이 과정은 애초에 비효율적이다.

sort가 되지 않은 데이터를 처리하는 과정이기 때문에!

---

나의 2차 시도는

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        int check = -1;
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for(int i=0;i<completion.length;i++) {
        	if(!participant[i].equals(completion[i])) {
        		check = i;
        		break;
        	}
        }
        if(check==-1){check=completion.length;}
        
        answer = participant[check];
        
        return answer;
    }
}

이렇게 Arrays.sort() 를 활용하는 방법이다

 

사실 이렇게 풀어도 아무 상관없을 것이다. 

 

하지만 문제의 카테고리가 hash인데 hash를 쓰지 않은 것이니까

넘어가보자.

---

마지막 해결방법

HashMap을 사용해보기!

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        
        HashMap<String, Integer> partMap = new HashMap<>();
        for(String player:participant) {
        	partMap.put(player, partMap.getOrDefault(player, 0)+1);
        }
        
        for(String player:completion) {
        	partMap.put(player, partMap.get(player)-1);
        }
        
        for(String key:partMap.keySet()) {
        	if(partMap.get(key)!=0)
        		answer = key; break;
        }
        
        return answer;
    }
}

HashMap<String, Integer> 타입을 만들어서 key에는 participant 플레이어 이름을 넣고 value에서는 동명이인 숫자를 넣어준다.