문제
처음에 작성한 코드
def solution(participant, completion):
for i in range(len(completion)):
for j in range(len(participant)):
if participant[j] == completion[i]:
participant.pop(j)
break
return participant[0]처음에 작성한 코드는 단순하게 completion를 기준으로 이중for문을 돌려서 같은 원소가 있으면 participant에서 pop했다. pop도 마지막 원소가 아닌 j번째 요소를 pop(j)하기 때문에 코드를 작성하면서도 백준이면 100% 시간초과 떴을텐데 좀 더 효율적인 방법이 없을지 고민했다.
역시나 효율성테스트에서 5개의 케이스 모두 실패로 떴고, 다음으로 생각해 본 풀이는 집합(set)이었고, 그다음은 정렬이었다. 집합의 경우 동명이인이 있기 때문에 중복되는 원소를 제거할 것이고, 적절한 풀이는 아니라고 생각했다. 정렬 코드는 아래와 같다.
두번째 시도
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]정렬로 풀이가 가능한 이유는 조건에 따라 completion의 길이는 participant의 길이보다 1 작은데 participant에서 하나의 원소를 제외하면 completion과 동일하기 때문이다. 정렬 후 비교를 하는데 completion 길이 내에서 다른 원소가 발견되면 바로 리턴하고, 그렇지 않으면 participant의 마지막 원소를 리턴한다.
최종 코드
def solution(participant, completion):
participant.sort() # 정렬이 핵심!
completion.sort()
for p, c in zip(participant, completion):
if p != c:
return p
return participant[-1] # 마지막인덱스에(zip객체에서 제외된 인덱스) 완주하지 못한 선수가 있는 경우 여기서의 핵심은 participant와 completion 리스트를 정렬한 것이다.
사실 정렬까지만 생각해봤는데 다른 사람의 풀이를 보니 zip을 사용한 것을 볼 수 있었다.
zip은 오늘 새롭게 알게된 것이다. 정렬과 함께 사용하면 유용하게 쓸 수 있을 것 같다.
💡 zip : 배열을 같은 인덱스끼리 짝지어준다. 만약 배열의 길이가 다를 경우 같은 인덱스끼리만 짝지어주고, zip 객체에서 나머지 인덱스는 제외된다.
Android Developer.