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

- 최종코드

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;

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

        for(int i = 0 ; i < completionList.size() ; i++) {
            if(!completionList.get(i).equals(participantList.get(i))){
                return answer = participantList.get(i);
            }
        }
        //for문에서 답이 나오지않은 경우, 배열의 마지막 참가자가 곧 완주하지 못한선수
        answer = participantList.get(participantList.size()-1);	
        
        return answer;
    }
}

- 중간코드

import java.util.Arrays;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        Arrays.sort(participant);
        Arrays.sort(completion);
        for(int i = 0 ; i < completion.length ; i++) {
            if(!completion[i].equals(participant[i])){
                return answer = participant[i];
            }
        }
        //for문에서 답이 나오지않은 경우, 배열의 마지막 참가자가 곧 완주하지 못한선수
        answer = participant[participant.length-1];
        
        return answer;
    }
}

- 실패코드

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        
        for(String n : participant) {
            if(!isComplete(n, completion)) {
                answer = n;
                break;
            }      
        }
        return answer;
    }
    
    public boolean isComplete(String s, String[] c) {
        for(int i = 0 ; i < c.length ; i++) {
            if(s.equals(c[i])) {
                c[i]="";        //동명이인 선수 방지
                return true;
            }
        }
        return false;
    }
}

- 최종코드와 중간코드의 테스트 결과

- 막혔던점 & 해결방법

1. 실패코드로는 정확성 테스트에서 통과하였으나 효율성 테스트에서 실패하였다. participant배열과 completion배열이 아주 큰 경우 이중 for문으로 인해 시간 복잡도는 O(n²)이므로 시간 초과가 된 것이다. 이를 해결하기 위해 이중 for문을 제거하고 completion의 길이가 participant의 길이보다 1 작으므로, 각각의 배열을 정렬한 후 같은 위치의 값을 비교하여 일치하지 않는 경우를 찾도록 수정하였다.
2. 중간코드로 효율성 테스트를 통과하였으니 여기서 멈추어야겠지만, 좀 더 시간을 줄일 수 있는 방법에 대해 고민하였다. Arrays클래스의 기본 제공 sort() 메소드는 Dual-Pivot Quicksort방식으로 정렬을 하므로 평균 O(nlog(n))의 시간복잡도를 가지며 최악의 경우 O(n²)이 된다. 반면 Collections클래스의 기본 제공 sort() 메소드는 Timsort방식으로 삽입 정렬과 합병정렬을 결합하여 만든 정렬방식이다. Timsort의 시간복잡도는 평균 O(nlog(n)) 이며 최악의 경우도 O(nlog(n))이다. 정렬방식의 변경을 통해 좀더 나은 효율성을 확보하였다.

- 아쉬운점

효율성 테스트에서 보듯 정렬방식의 변경으로는 최대 약30%에 불과한 속도 향상이 있었다. 좀 더 공부를 하여 더 나은 방식으로 더 많은 시간을 단축시켜보고싶다.