99클럽 코테 스터디_4기 11일차 TIL

 

TODAY TIL

안녕하세요! 오늘은 마라톤에 참여한 선수 중 단 한 명의 완주하지 못한 선수를 찾는 문제를 해결하는 방법을 다뤄보겠습니다. 이 문제는 코딩 테스트에서 자주 나오는 유형으로, 배열과 정렬을 다루는 좋은 연습이 됩니다.

 

문제 설명

수많은 마라톤 선수들이 마라톤에 참여했는데, 단 한 명의 선수를 제외하고는 모두 완주했습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어졌을 때, 완주하지 못한 선수의 이름을 반환하는 함수를 작성하세요.

제한사항

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

문제 해결 방법

이 문제를 효율적으로 풀기 위해 정렬을 사용한 방법을 설명하겠습니다.

해결 방법 순서

1. participant와 completion 배열을 정렬합니다.
2. 정렬된 상태에서 두 배열을 처음부터 비교하면서 일치하지 않는 요소를 찾습니다.
3. 만약 모든 요소가 일치하면 participant 배열의 마지막 요소가 완주하지 못한 선수입니다.

 

코드 구현

def solution(participant, completion):
    participant.sort()  # 참가자 배열 정렬
    completion.sort()   # 완주자 배열 정렬
    
    # 정렬된 배열에서 비교
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    
    # 마지막 참가자가 완주하지 못한 경우
    return participant[-1]

 

예제 테스트

예제 #1:

print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))  # 결과: "leo"

 

예제 #2

print(solution(["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]))  # 결과: "vinko"

 

예제 #3:

print(solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]))  # 결과: "mislav"

 

코드 설명

• participant와 completion 배열을 정렬하여 순서를 맞춥니다.
• 두 배열을 비교하며 첫 번째로 다른 이름을 반환합니다.
• 만약 모든 이름이 일치하면 participant 배열의 마지막 이름을 반환합니다. 이는 정렬된 completion 배열의 마지막 요소와 비교했을 때, 남는 한 명이기 때문입니다.

시간 복잡도

이 솔루션은 정렬에 의해 O(nlog⁡n)O(n \log n)O(nlogn)의 시간 복잡도를 가집니다. nnn은 participant 배열의 길이입니다.

마무리

이 방법은 배열 정렬과 비교를 사용하여 효율적이고 직관적인 솔루션을 제공합니다. 동명이인이 있어도 정확히 동작하도록 설계되었습니다.