문제 바로가기

나의 첫번째 풀이

정확성 테스트만 통과하고 효율성 테스트를 통과하지 못한 나의 첫번째 풀이이다. 효율성을 그나마 끌어올리고자 binarySearch를 활용하였으나 100,000명의 마라톤 선수를 매번 탐색하는 것 자체가 효율적이지 못했나보다.

import java.util.*;

class Solution {
    public static String solution(String[] participant, String[] completion) {
        String answer = "";
        Arrays.sort(participant);
        List<String> participants = new ArrayList<>(Arrays.asList(participant));

        for (String s : completion) {
            if (Arrays.binarySearch(participant, s) != -1) {
                participants.remove(s);
            } else {
                break;
            }
        }
        return participants.get(0);
    }
}

---

나의 두번째 풀이

탐색 과정에서 시간 복잡도 O(log n)을 가지는 Map을 사용하면 binarySearch를 사용하는 List보다 효율성이 더 높을 것이라 생각하였다.

• map, set
  삽입, 삭제, 탐색 모두 시간 복잡도 O(log n)
• list
  지정된 위치의 삽입과 삭제는 모두 시간 복잡도 O(1)
  탐색 및 임의 원소 접근은 모두 시간 복잡도 O(n)
• vector
  삽입과 삭제, 탐색 모두 시간 복잡도 O(n)
  임의 원소 접근은 시간 복잡도 O(1)

결과는 성공이었다. 다만 코드가 다소 지저분하고, Map을 제대로 활용하진 못한것으로 보인다. 다른 사람들의 풀이도 참고해보자.

import java.util.*;

class Solution {
    public static String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> repo = new HashMap<>();
        for (String s : participant) {
            repo.computeIfPresent(s, (String key, Integer value) -> ++value);
            repo.putIfAbsent(s, 1);
        }
        for (String s : completion) {
            if (repo.containsKey(s) && repo.get(s) != 0) {
                if (repo.get(s) == 1) {
                    repo.remove(s);
                } else {
                    repo.put(s, repo.get(s) - 1);
                }
            } else {
                return s;
            }
        }
        for (String s : repo.keySet()) {
            answer = s;
        }
        return answer;
    }
}

---

다른 사람의 풀이 1

김진욱님 외 284명의 풀이를 참고했습니다.이렇게 해시를 사용할 수 있구나하고 소름이 돋았고, 아직 배울 것이 너무 많다는 것을 다시 한번 느꼈다.

우선 participant 모두를 map에 등록하는데, 단순한 get이 아닌 getOrDefault를 활용하였기에 없으면 0 + 1이 되어 1을 value값으로 할당하고, 존재하면 그 값을 받아와 1을 더해주는 식으로 할당하는 것이다.

이후 completion에서 받아온 선수들을 key값으로 해서 value값을 -1 해준다. Map은 put으로 값의 수정이 가능하기 때문이다.

단 한명만 완주하지 못하였으므로 value 값이 1인 단 한명이 존재할 것이고 그 선수를 반환해주는 것이다.

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;
            }
        }
        return answer;
    }
}

---

다른 사람의 풀이 2

이진성님 외 500명의 풀이도 가져왔습니다. 효율성때문에 배열을 사용하면 안된다는 저의 생각을 한번 더 깨부순 풀이입니다.. 😂

결국 participant와 completion 배열안의 선수들 이름은 1명빼고 일치할 것이므로 두 배열 모두 정렬을 하고, 하나씩 비교를 하는 것이 이 풀이의 핵심이다.

다음에 해시 관련 효율성 테스트 문제를 풀 때도 배열을 이용한 풀이가 가능한 지 확인해봐야겠다.

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

            if (!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        return participant[i];
    }
}