[프로그래머스][파이썬/Python] 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

입출력 예

 

풀이 과정

1. 최종 제출 코드와 테스트 결과 (통과)

def solution(participant, completion):
    participant.sort()
    completion.sort()
    completion.append('tmp')
    for i in range(0, len(participant)):
        if participant[i] != completion[i]:
            break
    return participant[i]

 

리스트 completion 에 'tmp'를 append 한 이유?

리스트 completion의 길이는 항상 리스트 participant의 길이보다 1만큼 작으며, 그 때문에 for문에서 participant[i]와completion[i]를 비교할 때 list index out of range 에러가 발생한다. 이러한 에러를 방지하기 위해서는 두 리스트의 길이를 동일하게 맞춰주어야 하며, 그러한 이유로 리스트 completion에 더미 요소 하나를 추가해주었다.

 

 

새로운 발상?

0번째 인덱스부터 비교를 하며 반복할 때, comletion의 마지막 요소까지 반복했음에도 불구하고 if문에 걸리는 것이 없다면 participant의 마지막 요소가 완주하지 못한 선수일 것이다. 더미 요소를 추가하지 않고서도 그것을 캐치해냈다면 더 좋았을 것 같다는 생각이 들었다. 그래서 생각해낸 코드는 아래와 같은데, 기존 코드에 비해 깔끔하지는 않은 것 같다. 오히려 for문 안에 비교문이 한 번 더 들어가 시간복잡도만 늘리는 꼴이 된 것 같다. 실제로 정확성/효율성 테스트에서도 평균적으로 더 좋지 못한 결과를 보여줬다.

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

 

2. 통과 전 시도했던 코드들과 반성의 시간들

 

# 1차 코드

def solution(participant, completion):
    tmp = participant
    for i in range(0, len(participant)):
        if participant[i] in completion:
            tmp.remove(participant[i])
            completion.remove(participant[i])
    return tmp

정말 부끄러운 코드인데 반성좀 하자는 마음으로 기록을 남긴다. python을 너무 오랜만에 만진 탓에 아주 기본적이지만 중요한 것을 간과했다.

 

python에서는 다른 변수에 기존의 리스트를 할당해줄 때, 기존의 리스트가 다른 변수에 복사가 되는 것이 아니다. 기존의 리스트를 할당받은 다른 변수는 기존의 리스트를 참조할 뿐이며, 완전히 똑같은 리스트라고 볼 수 있다. 즉, 기존의 리스트를 담은 변수와 리스트를 복사해 담고자 했던 다른 변수는 동일한 객체를 가리키게 되는 것이다.

 

a = [1, 2, 3] 이라는 리스트가 있었고 새로운 변수 b에 a를 복사하려고 b = a 라는 한 줄을 짰다고 하자. 이 경우, b는 리스트 a와 동일한 id를 갖게 된다. 그 결과, 리스트 a에서 요소를 추가하거나 제거하거나 정렬을 하는 등의 행위를 할 경우 b라는 리스트에도 똑같이 영향이 간다.

 

그래서 리스트를 복사해주고 싶을 때는 리스트 전체 요소를 가리키는 [:] 를 쓰거나 copy모듈을 활용해야 한다. 다음 코드는 [:]를 활용하는 간단한 예시이다.

a = [1, 2, 3]
b = a[:]

그래서 위와 동일한 방식으로 tmp = participant[:] 로 두 번째 줄을 바꾸고 VS에서 돌려보니 잘 됐다. 근데 프로그래머스에 제출할 때는 결과값이 다르다고 한다. 이건 대체 왜 그런 건지 잘 모르겠지만 아무튼 이상한 코드니까 그런 거겠지 싶어서 다른 아이디어를 떠올렸다.

 

 

# 2차 코드

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(0, len(participant)):
        if participant[i] == completion[i]:
            participant.remove(participant[i])
            completion.remove(completion[i])
        else:
            break
    return participant[i]

이제서야 '정렬한 후 각 리스트의 원소를 비교하면 되겠구나' 싶었다. 그런데 list index out of range 에러가 발생했다. completion의 원소 개수를 participant와 맞춰줘야겠다 생각하고 세 번째 줄 아래에 completion.append('tmp') 를 추가해줬더니 입출력 예시는 다 통과했다. 하지만 제출해보니 테스트 결과가 처참했다.

테스트 결과를 보고 나니 그제서야 굳이 remove를 할 필요가 없다는 생각이 들었다. 시간복잡도만 늘리는 꼴이 되기 때문이다. 그래서 remove하는 두 줄을 지우고 코드를 약간 다듬어 최종 제출 코드를 완성시켰다. 하지만... 최종 제출 후 이 문제를 단 네 줄 만에, 엄밀히 따지자면 단 두 줄 만에 해결해버린 걸 보고 내 코드가 너무 비루해보였다ㅠㅠㅠ 대단한 분들이 역시 많다.

 

아. 진짜 너무 못해졌다. 아무리 바빠도 하루 혹은 이틀에 걸쳐서라도 한 문제 씩은 풀어야겠다.

 

 

 

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