[프로그래머스] 완주하지 못한 선수

▶문제설명 (출처 : https://programmers.co.kr/learn/courses/30/lessons/42576?language=java)

---

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

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

제한사항

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

[첫 번째 채점]

import java.util.*;
 
class Solution {
 
    public String solution(String[] participant, String[] completion) {
        List<String> list = new ArrayList<String>();
        Collections.addAll(list, participant); // ArrayList에 participant 요소들 저장
        
        int p_length = participant.length;
        Map<String,Integer> hashtable = new HashMap<String,Integer>();
        
        int cnt = 0;
        for(int i = 0 ; i < p_length ; i++){
            if(!hashtable.containsKey(participant[i])){
                //해시맵에 participant[i]를 키값으로 put
                hashtable.put(participant[i], cnt++);
            }
        }
        for(int i = 0 ; i < p_length-1 ; i++){
            String str = completion[i];
            if(hashtable.containsKey(str)){
                //해시맵에 존재하는 경우(완주한사람 이름이 list에 존재하는 경우)
                list.remove(str); // list에서 삭제
            }
        }
         // 모두 삭제되고 하나 남은 이름이 완주하지 못한 참여자
        answer += list.get(0);
        return answer;
    }
 
}

채점 결과

정확성: 50.0

효율성: 00.0

합계: 50.0 / 100.0

효율성 테스트에서 시간 초과라는 결과가 나왔다.

---

[두 번째 채점]

import java.util.*;
 
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        int p_length = participant.length;
        Map<String,Integer> hashtable = new HashMap<String,Integer>();       
 
        int cnt = 0;
        for(int i = 0 ; i < p_length-1 ; i++){
            if(!hashtable.containsKey(completion[i])){
                //해시맵에 completion[i]요소를 put
                hashtable.put(completion[i], cnt++);
            }
        }
        for(int i = 0 ; i < p_length ; i++){
            String str = participant[i];
            if(!hashtable.containsKey(str)){
                //해시맵에 participant[i]키가 존재하지 않는 경우
                answer += str;
                break;
            }
        }
        return answer;
    }
}

입력값 〉	["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]
기댓값 〉	"mislav"
실행 결과 〉	실행한 결괏값 []이(가) 기댓값 [mislav]와(과) 다릅니다.

채점 결과

정확성: 30.0

효율성: 40.0

합계: 70.0 / 100.0

참여자들 중에 동명이인이 존재하고, 동명이인이 완주하지 못한 경우를 해결하지 못했다.

이 문제를 해결하기 위해서, 또 고민하는 과정이 필요했다.

---

[세 번째 채점]

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

채점 결과

정확성: 50.0

효율성: 50.0

합계: 100.0 / 100.0

HashMap을 사용하지 않고 배열 정렬을 통해 해결하는 것이 가능했다.