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

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant											completion											return
["leo", "kiki", "eden"]								["eden", "kiki"]									"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]			"vinko"
["mislav", "stanko", "mislav", "ana"]				["stanko", "ana", "mislav"]							"mislav"

문제 풀이

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        List<String> list1 = new LinkedList<>(Arrays.asList(participant));
  
        for(int i=0; i<completion.length; i++){
            if(list1.get(0).equals(completion[i])) list1.remove(completion[i]);
        }
        return list1.get(0);
    }
}

---

실패한 문제풀이

import java.util.*;

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

띠용? 오 완전 쉽네 하고 풀었는데 이게 무슨 일? 효율성 테스트에 실패했다. 정확성 테스트에서는 금방 걸렸는데..? 아무래도 ArrayList에 구현된 메서드들의 시간복잡도가 문제라는 생각이 들었다. 그래서 ArrayList보다 remove() 연산이 빠른 LinkedList로 바꿔 봤는데도 띠용 채점 점수만 2점 올라가고 여전히 효율성 테스트는 실패다. 의문인 것이 ArrayList와 LinkedList의 contains()의 시간복잡도는 O(n)으로 같다. 그럼 확실히 코드 속도는 개선이 된 것인데..그래서 점수가 2점만 올라간 것일까..^^
그러면 함수의 시간 복잡도가 상수로 나오도록 해야 하는 것인가하는 의심이 든다. contains( )가 간결하고 편해서 좋긴 하지만 데이터가 증가하는만큼 속도도 증가하니 그냥 get().equals를 사용하기로 했다. 아 그리고 두 배열을 비교해야 하기 때문에 처음에 sort를 해주는 것도 추가하였다. 그리고나서.. 채점 완료! 이 문제는 시간복잡도를 생각하는 것이 포인트인 문제였나보다.

---

정리

시간복잡도: 컴퓨터 프로그램의 입력값과 수행 시간의 상관 관계를 나타내는 척도

출처

• http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html