프로그래머스 : 완주하지 못한 선수 (42576)

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

오늘도 알고리즘 몇문제 풀었다.

입력값으로는 마라톤에 참여한 선수와 골인한 선수가 주어진다.

출력값으로는 완주하지 못한 선수 이름을 출력해야 한다.

 

set으로 구현해보려 했으나 중복선수가 존재하여 바로 포기했고,

일단 기능을 먼저 구현해보고자 하여 2중for문을 사용해서 구현했으나, 시간복잡도 문제로 인해 해결하지 못했다.

그래서 for문보다 contains가 더 빠르지 않을까 라는 생각에 List로 받아서 contains를 사용했다.

하지만 contains는 set과 map을 쓸 때 사용하여 빠르게 느껴졌을 뿐,

찾아보니 contains와 for문은 무려 같은 기능을 가진것이었다!

조금만 생각하면 알 수 있는 부분이었지만 하루종일 알고리즘 문제만 풀다보니 멍해졌던 것 같다.

도저히 정답을 모르겠어서 반쯤 포기한 상태로 문제를 다시한번 읽으니, 단 한명의 선수만 완주하지 못한다고 한다!

그래서 정렬 후, 참여자, 완주자를 정렬 후 이름을 비교하여 찾아보기로 했다.

 

최종코드

import java.util.*;
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 (!participant[i].equals(completion[i])) {
                answer = participant[i];
                break;
            }
        }

        if (answer.isEmpty()) {
            answer = participant[participant.length - 1];
        }

        return answer;
    }
}

 

정답이었다 ! 하지만 기쁨보다는 sort는 어떤 알고리즘을 사용하길래 정렬하는데에 시간복잡도가 낮은지 의문이었다.

찾아보니 sort는 TimSort 알고리즘을 사용하며,

TimSort는 삽입 정렬(Insertion Sort)과 병합 정렬(Merge Sort)을 결합하여 사용하고 있었다.

오늘도 삽질로 시간을 많이 보내서 아쉬웠지만, sort가 어떤 알고리즘을 사용하는지 알게되어 나쁘지 않았다.

다음번엔 병합정렬을 직접 코드로 구현해 봐야겠다.