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

완주하지 못한 선수

---

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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 LinkedList<>();
        
        for(int i = 0 ; i<participant.length ; i++){
            list.add(participant[i]);
        }
        
        for(int i = 0; i<completion.length; i++){
            if(list.contains(completion[i])){
                list.remove(completion[i]);
            }
        }
        
        return list.get(0);
    }
}

위의 코드처럼 제출을 하면 정확성 테스트는 모두 통과되는 것을 확인할 수 있다. 하지만 효율성 테스트에서 모두 시간 초과가 발생한다.

이 문제점을 해결하기 위해서 시간 복잡도에 대해 검색해보았다. 그리고 자바에서 제공하는 자료구조들은 각각의 시간복잡도를 가진다는 것을 알게 되었다.

코드를 살펴보면, 총 2개의 반복문이 나오는 것을 볼 수 있다. 그렇기 때문에 마라톤 참여 선수가 최대 10만이기 때문에 for문 한번에 1/1000초가 걸린다고 생각하여 시간초과가 발생할 줄 몰랐다.

하지만 검색을 통해 LinkedList의 add함수는 O(1)이고, contains함수는 O(n), remove함수는 O(n)인 것을 알 게 되었다.

이처럼 첫 번째 for문은 add함수가 O(1)이므로, O(n)이고, 두 번째 for문은 contains함수는 O(n), remove함수는 O(1)으로 O(n^2)입니다. 그렇기 때문에 전체 시간 복잡도는 O(n) + O(n^2)으로 O(n^2)로 n이 10만이므로 100초가 소요된다.

검색을 통해서 해당 문제는 O(n) 시간복잡도를 이용해서만 문제를 풀어야한다는 것을 알게 되었다 !!

근데 고민 끝에 너무 모르겠어서.. 인터넷의 도움을 받아 풀이 방법만 참고하여 풀어보았습니다..

성공 코드

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        List<String> p_list = new ArrayList<>();
        List<String> c_list = new ArrayList<>();
        String rs = ""; 
        
        for(int i = 0 ; i<participant.length; i++){
            p_list.add(participant[i]);
        }
        
        for(int i = 0 ; i<completion.length; i++){
            c_list.add(completion[i]);
        }
        
        Collections.sort(p_list);
        Collections.sort(c_list);
        
        for(int i = 0; i<c_list.size(); i++){
            if(!p_list.get(i).equals(c_list.get(i))){
                return p_list.get(i);
            }
        }
        
        return p_list.get(p_list.size()-1);
        
    }
}

해당 코드는 O(n)의 시간복잡도만을 사용해서 풀었다.
문제 접근 방법은 각 배열을 List에 담아서 정렬을 한 후 순차적으로 조회하여 값이 다를 때 반환하도록 구현하였다.

그리고 기존의 LinkedList는 조회(get)에 대해서 성능이 낮기 때문에 각 배열들을 ArrayList에 담아 사용했다.

또한 정렬하는데 있어서도 Arrrays.sort()와 Collections.sort()중 최악의 경우 시간복잡도가 더 낮은 Collections.sort()를 사용하여 정렬을 하였다.

마지막 for문에서는 index범위 에러를 피하기 위해 길이가 1 작은 완료 선수 리스트 길이 기준으로 반복하였다. 하지만 완주하지 못한 선수가 참가 선수 리스트에서 마지막 원소일 수 있기 때문에 if문을 사용하여 return 처리를 해주었다.