Programmers 코딩테스트 연습- 완주하지 못한 선수 python 문제풀이

역시 알고리즘 문제풀이는 파이썬이 답인 것 같다.

 

C++는 내가 추구하고자 하는 방향에 필요 없는 언어인것 같기도 하고...

현재로써 다른 공부할 것들이 많기 때문에...

익숙하면서도 편한, 숏 코딩에 좋은 파이썬을 쓰기로 했다.

예외처리에도 편하고, collection이 너무 사기여서

알고리즘 문제풀이는 무조건 파이썬으로 하는 게 좋은 것 같다...!

 

일단 이런 비교 문제는. 항상

 

1. n시간에 끝날 수 있는가?

O라면 선형 검색

X라면 Collection을 이용한 정렬 (Quick/Merge를 이용한 nlogn시간)

 

이 두 가지를 생각하는 게 핵심이다.

즉, 데이터 비교 == 정렬 이라고 생각하는 것이 좋다.

 

난 어떻게 접근했냐면...

일단 두 데이터를 정렬한다.

그러면 두 데이터의 len이 같다면... 무언가 다른 요소가 있을 것이고.

len이 다르다면... 중복 또는 부족이 존재할 것이다.

 

즉 idea는

정렬 후 앞에서부터 비교!

모자라면... 남은 input이 완주하지 못한 선수.

다르다면... 그녀석이 완주하지 못한 선수.

 

 

def solution(participant, completion):
	# 두 List를 정렬한다. O(nlogn)
    participant.sort()
    completion.sort()
    # 앞에서부터 비교한다. 차이가 있다면. 그 녀석이 범인이다.
    for i in range(0, len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    # 남는 요소가 있다면. 그 녀석이 범인이다.
    return  participant.pop()

 

이해가 안되는 분들을 위해... print 결과를 보면 이해가 빠르다.