[프로그래머스] 완주하지 못한 선수 Python (Level 1)

TITLE

문제주소 : https://programmers.co.kr/learn/courses/30/lessons/42576

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

 

---

<문제 설명>

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

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

 

<풀이법>

직관적으로 문제를 보면, 참여자 배열과 완주자 배열을 직접 비교해보면 됩니다. 나머지는 다 똑같고 단 한명만 차이가 있는 것이므로, 가장 단순한 방법은 이중 반복문을 사용하여 비교하는 방식입니다.하지만 이중 반복문을 사용할 경우 시간복잡도가 O(N^2)으로, 시간 복잡도를 더 줄일 수 있는 방법을 찾아보았습니.

 

그래서 찾아낸 방법이, 두 배열을 모두 정렬하고 인덱스에 맞춰서 비교하는 것입니다. 두 배열은 단 하나의 원소 말고는 전부 동일한 원소를 가지기 때문에 정렬된 상태에서 각 인덱스별로 비교를 하다가 동일하지 않은 원소가 나타난다면, 해당 참가자는 완주하지 못한 사람이 될 수 밖에 없습니다. 시간복잡도를 계산해보면, 각 배열 정렬에 걸리는 시간 O(NlogN) 이 각 배열에 적용되고, 이 둘을 비교하는 시간 O(N)이 적용되므로, 총 시간복잡도는 O(NlogN)으로 기존의 이중 반복문을 사용한 경우보다 좋은 결과가 나오게 됩니다.

 

<코드(Python)>

def solution(participant, completion):
    answer = ''
    participant.sort()
    completion.sort()
    for i in range(len(participant)):
        if i == len(participant)-1 or participant[i] != completion[i] :
            answer = participant[i]
            break;
    return answer

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest