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

문제 : programmers.co.kr/learn/courses/30/lessons/42576?language=java

코딩테스트 연습 - 완주하지 못한 선수

1. 정렬 이용
   1. participant, completion array를 정렬한다.
   2. 첫 번째 원소부터 차례대로 서로 다른 원소(이름)가 나올 때 까지 진행한다.
   3. 서로 다른 원소가 나오면 이 때의 participant의 원소를 반환한다.
2. Map 이용
   1. participant array로 부터 각 이름별 참가자의 수를 업데이트한다.
   2. completion array로 부터 각 이름별 참가자의 수를 제거한다.
   3. 마지막으로 남아있는 이름을 반환한다.

 

방법 1의 경우 정렬 연산에 따라 worst case로 O(n^2)의 time complexity를 가질 수 있는 것으로 보인다.

반면에 방법 2의 경우 worst case에도 hash function의 time complexity가 O(n) 이므로 결과적으로 O(n)의 time complexity를 가지게 된다. 

따라서, 방법 2가 방법 1보다 일반적으로 효율적일 것으로 생각할 수 있을 것이다.

 

프로그래머스에서의 테스트 결과에서는 효율성 테스트에서 정렬을 이용한 방법 1이 수백ms, Map을 이용한 방법 2가 수십ms 정도의 결과를 보여주며 예상했던 대로의 결과를 얻을 수 있었다.

 

Level 1 문제 답게 해결하는 것 자체는 매우 손쉬운 문제였다.

 

소스코드

1. 정렬 이용

import java.util.Arrays;

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

 

2. Map 이용

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> participants = new HashMap<>(); // 이름 : 해당 이름을 가진 참가자 수

        // 1. 참가자 인원 업데이트
        for (String name : participant) {
            participants.put(name, participants.getOrDefault(name, 0) + 1);
        }

        // 2. 완주자 제거
        for (String name : completion) {
            int count = participants.get(name);
            participants.replace(name, count, count - 1);
            participants.remove(name, 0);
        }

        return participants.keySet().iterator().next();
    }
}