[알고리즘]기초2-완주하지 못한 선수

완주하지 못한 선수

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

첫 번째 코드

def solution(participant, completion):
    answer = ''

    for i in range(len(participant)) :
        temp=participant[0]
        if temp not in completion:
            answer=temp
            break;
        else:
            participant.remove(temp)
            completion.remove(temp)
            
    return answer

👉🏻 for문 내부에 in 연산자를 이용하여 participant의 원소가 completion에 존재하는지 판단함

• 동명이인이 있을 경우 단순 in 연산자를 이용하면 판별하기 어려우므로 participant가 completion에 있다면 해당 원소를 participant와 completion에서 제거
• remove()를 이용하면 중복되는 원소라고 하더라도 하나만 삭제된다.
  
  

😥 정확성 테스트는 통과하였으나 효율성 테스트에서 탈락함

• 경기에 참여산 선수의 수가 최대 100,000명 이므로 최대 nlogn의 시간복잡도를 가져야 하는데 for문 내부에 in 연산자를 넣어 n^2 시간 복잡도를 가지게 됨
  
  

두 번째 코드

def solution(participant, completion):
    answer = ''
    
    p_copy=sorted(participant)
    c_copy=sorted(completion)
    
    for i in range(len(c_copy)):
        if (p_copy[-1]!=c_copy[-1]):
            answer=p_copy[-1]
            break;
        else :
            p_copy.pop()
            c_copy.pop()
            
    if len(p_copy)==1 and len(c_copy)==0:
        answer=p_copy[-1]
        
    return answer

👉🏻participant와 completion을 모두 정렬한 후 원소 비교

• participant와 completion 모두 정렬하였으므로 같은 index의 원소끼리 비교하여 같은 값인지 판별

• 마지막 원소부터 비교 후 다른 값이면 해당 값을 answer로 반환

• 같은 값이면 pop()하기

• for문을 마친 후 participant에 남은 원소가 있다면 해당 원소를 answer로 반환

  ❓ for문의 원소 비교를 끝에서부터 하지 않고 0부터 한 후 pop(0)으로 하면 시간초과 탈락이 된다.

  • 👉🏻pop()과 pop(-1)은 시간복잡도 O(1)이지만 pop(i)는 O(n)의 시간복잡도를 가짐! 참고로 remove(i)도 O(n)의 시간복잡도를 가짐