[코딩테스트] 완주하지 못한 선수

문제

---

완주하지 못한 선수 문제 바로가기

제출 코드(JAVA)

---

첫번째 코드 제출

import java.util.Arrays;

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

간단하게 배열들 정렬하여, index가 다를 시 값을 return하도록 했다.

효율성 테스트

테스트 1 〉	통과 (0.45ms, 52.7MB)
테스트 2 〉	통과 (0.30ms, 52.9MB)
테스트 3 〉	통과 (5.69ms, 55MB)
테스트 4 〉	통과 (7.20ms, 53.4MB)
테스트 5 〉	통과 (6.23ms, 53.1MB)
효율성  테스트
테스트 1 〉	통과 (146.61ms, 81.4MB)
테스트 2 〉	통과 (269.48ms, 88.7MB)
테스트 3 〉	통과 (370.67ms, 93.7MB)
테스트 4 〉	통과 (285.83ms, 95.6MB)
테스트 5 〉	통과 (379.35ms, 94.8MB)

두번째 코드 제출

import java.util.*;

class Solution {
    public String solution(String[] participants, String[] completions) {
        String answer = "";
        HashMap<String, Integer> playerMap = new HashMap<>();
        for (String player : participants) playerMap.put(player, playerMap.getOrDefault(player, 0) + 1);
        for (String player : completions) playerMap.put(player, playerMap.get(player) - 1);

        for (Map.Entry<String, Integer> entry : playerMap.entrySet()) {
            if (entry.getValue() != 0){
                return entry.getKey();
            }
        }
        return null;
        
    }
}

sort에서 드는 비용이 커 HashMap과 Entry를 사용해, 비용을 절감하도록 구성했다.

효율성 테스트

테스트 1 〉	통과 (0.06ms, 51.8MB)
테스트 2 〉	통과 (0.07ms, 52.2MB)
테스트 3 〉	통과 (0.74ms, 52.7MB)
테스트 4 〉	통과 (1.29ms, 53.5MB)
테스트 5 〉	통과 (1.31ms, 53.5MB)
효율성  테스트
테스트 1 〉	통과 (43.51ms, 81.7MB)
테스트 2 〉	통과 (78.32ms, 87.8MB)
테스트 3 〉	통과 (110.35ms, 98.6MB)
테스트 4 〉	통과 (105.02ms, 95.6MB)
테스트 5 〉	통과 (76.63ms, 96.2MB)

소요시간이 대략 3~4배정도 단축되었다..!

제출 코드(Python)

---

첫번째 코드 제출

def solution(participants, completions):
    participants.sort()
    completions.sort()
    for i in range(0, len(completions), 1):
        print(i, completions[i], participants[i])
        if completions[i] != participants[i]:
            return participants[i]
    return participants.pop()

java로 한번 풀었기 때문에 그를 기반으로 작성했다

효율성 테스트

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.27ms, 10.3MB)
테스트 4 〉	통과 (0.77ms, 10.4MB)
테스트 5 〉	통과 (0.55ms, 10.3MB)
효율성  테스트
테스트 1 〉	통과 (36.91ms, 18MB)
테스트 2 〉	통과 (57.39ms, 22.2MB)
테스트 3 〉	통과 (78.75ms, 24.8MB)
테스트 4 〉	통과 (90.92ms, 26.4MB)
테스트 5 〉	통과 (81.99ms, 26.4MB)

두번째 코드 제출

def solution2(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

Counter 객체는 빼기도 가능하다,,, 갓 python,,,,

효율성 테스트

정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.2MB)
테스트 2 〉	통과 (0.04ms, 10.2MB)
테스트 3 〉	통과 (0.39ms, 10.3MB)
테스트 4 〉	통과 (0.79ms, 10.5MB)
테스트 5 〉	통과 (0.69ms, 10.4MB)
효율성  테스트
테스트 1 〉	통과 (28.58ms, 24.4MB)
테스트 2 〉	통과 (44.33ms, 27.8MB)
테스트 3 〉	통과 (53.50ms, 30.2MB)
테스트 4 〉	통과 (106.60ms, 39.1MB)
테스트 5 〉	통과 (75.54ms, 39MB)

하지만 속도 관련에서는 눈에 띄는 차이는 보이지 않는 것 같다

세번째 코드 제출

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

hash값을 사용한 결과값 도출

효율성 테스트

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.36ms, 10.3MB)
테스트 4 〉	통과 (0.77ms, 10.3MB)
테스트 5 〉	통과 (0.42ms, 10.4MB)
효율성  테스트
테스트 1 〉	통과 (22.41ms, 24MB)
테스트 2 〉	통과 (39.01ms, 28.2MB)
테스트 3 〉	통과 (48.16ms, 31.4MB)
테스트 4 〉	통과 (49.39ms, 37.6MB)
테스트 5 〉	통과 (49.92ms, 37.8MB)

특정 값에 따른 hash로 해결하는 방법에 감탄하고 또 하나 배워간다