완주하지 못한 선수

문제

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

--

풀이

1. ArrayList에 참여자들의 이름을 넣고, 완주자들의 이름이 포함되어있는지 확인한다.
2. 만약 포함되어 있다면 삭제하여 마지막에 남은 참여자 이름을 반환한다.

import java.util.ArrayList;

class Solution {
    public String solution(String[] participant, String[] completion) {
        ArrayList<String> participants = new ArrayList<>();
        for (int i=0; i<participant.length; i++){
            participants.add(participant[i]);
        }
        
        for (int i=0; i<completion.length; i++) {
            if (participants.contains(completion[i])) {
                participants.remove(completion[i]);
            }
        }
        
        return participants.get(0);
    }
}

정확성 테스트
테스트 1 〉	통과 (0.04ms, 80.1MB)
테스트 2 〉	통과 (0.04ms, 71.4MB)
테스트 3 〉	통과 (2.94ms, 85.9MB)
테스트 4 〉	통과 (12.26ms, 86.9MB)
테스트 5 〉	통과 (7.76ms, 94.6MB)
테스트 6 〉	통과 (0.02ms, 73MB)
테스트 7 〉	통과 (0.03ms, 77.2MB)

정확성은 통과하였지만, 효율성에서 통과하지 못했다.

다른 방법을 생각해보자..

---

Set 이용하기

HashSet을 이용하면 데이터를 가져오는 속도가 훨씬 빨라질 것이다.
하지만 여기서 문제점은 동명이인도 생각해야 한다는 점이다.

그렇다면 HashMap을 사용해보자.

1. HashMap<String, Integer>에 완주자의 이름과 명수를 같이 기록한다.

2. 참여자들의 이름 중 HashMap에 존재하는 이름의 명수를 하나씩 줄이고 0이 되면 HashMap에서 제외한다.

3. 만약 HashMap에 존재하는 이름이 없다면 그 사람이 완주를 하지 못한 사람이다.
   (동명이인이라도, 2명이 완주했지만 3명이 참여했다면 마지막 동명이인3이 HashMap을 확인할 때는 1,2가 이미 HashMap의 명수를 0으로 만들어서 찾을 수 없는 상태일 것이다)

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> numOfCompletion = new HashMap<>();
        
        //완주자 정보 넣기
        for (int i=0; i<completion.length; i++) {
            String name = completion[i];
            int num = 1;
            if (numOfCompletion.containsKey(name)){
                num = numOfCompletion.get(name) + 1;
            }
            numOfCompletion.put(name, num);
        }
        
        
       	//참여자의 정보를 확인하면서 명수 줄이기
        String result = "";
        for (int i=0; i<participant.length; i++) {
            String name = participant[i];
            if (numOfCompletion.containsKey(name)) {
                int num = numOfCompletion.get(name) - 1;
                if (num == 0) { //0이라면 완주한 모든 참여자 확인 
                    numOfCompletion.remove(name);
                } else { //아직 동명이인 존재
                    numOfCompletion.put(name, num);
                }
            } else { //만약 key를 찾을 수 없다면 완주하지 못한 사람
                result = name;
                break;
            }
        }
        return result;
    }
}

정확성  테스트
테스트 1 〉	통과 (0.04ms, 86.9MB)
테스트 2 〉	통과 (0.07ms, 72.7MB)
테스트 3 〉	통과 (0.30ms, 80.8MB)
테스트 4 〉	통과 (2.06ms, 81.2MB)
테스트 5 〉	통과 (0.51ms, 73.6MB)
테스트 6 〉	통과 (0.01ms, 82MB)
테스트 7 〉	통과 (0.02ms, 80MB)
효율성  테스트
테스트 1 〉	통과 (29.72ms, 88.9MB)
테스트 2 〉	통과 (53.59ms, 94.9MB)
테스트 3 〉	통과 (59.65ms, 97MB)
테스트 4 〉	통과 (50.64ms, 97.1MB)
테스트 5 〉	통과 (69.56ms, 97.5MB)

Set을 사용하니 더 빨라진 모습을 볼 수 있다.

---

코드 줄이기

Iterator를 사용하고, HashMap의 메서드 중 getOrDefault를 사용하면 코드를 더 짧게 줄일 수 있다.

getOrDefault(key, a) 함수는 만약 key에 해당하는 Value가 있으면 가져오고, 없으면 a를 쓰겠다는 메서드이다.

이후 완주자를 확인할 때 같은 Key(이름)이 있다면 value값(명수)을 하나씩 줄이고
최종적으로 HashMap을 살펴보았을 때, value가 0이 아닌(사실상 1이 남을 것이다) key, 이름을 반환하면 된다.

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);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
                break;
            }
        }
        return answer;
    }
}

정확성  테스트
테스트 1 〉	통과 (0.05ms, 76.8MB)
테스트 2 〉	통과 (0.08ms, 67.9MB)
테스트 3 〉	통과 (0.53ms, 76.8MB)
테스트 4 〉	통과 (0.80ms, 91.3MB)
테스트 5 〉	통과 (0.74ms, 90.1MB)
테스트 6 〉	통과 (0.05ms, 88.2MB)
테스트 7 〉	통과 (0.05ms, 86.8MB)
효율성  테스트
테스트 1 〉	통과 (33.72ms, 83.1MB)
테스트 2 〉	통과 (71.11ms, 90.4MB)
테스트 3 〉	통과 (75.37ms, 99.2MB)
테스트 4 〉	통과 (79.09ms, 96.6MB)
테스트 5 〉	통과 (78.04ms, 97.8MB)

성능적으로는 위에 코드가 더 좋지만, 가독성이 훨씬 좋다.

---

가독성을 가질 것인지, 성능을 가질 것인지에 대한 선택은..
테스트만 통과한다면 자유인 것 같다.