[문제출처 : Codechef] 제가 정말 좋아하는 노래가 있습니다. 이 노래는 현재 playlist의 K번째에 위치하고 있습니다. 그런데 제가 실수로 이 리스트를 인덱스 순으로 정렬해버렸다고 했을 때, 제가 정말 좋아하는 노래는 새로운 playlist의 몇번째에 위치하고 있을까요?
예를들면, [1, 3, 4, 2]의 index를 갖는 playlist가 있다고 가정할 때, 제가 가장 좋아하는 노래가 2번째에 있었다면, 그것의 index는 3이므로 index순으로 정렬된 새로운 playlist에서는 3번째에 위치하고 있을 것입니다.
이 문제는 함정에 빠지기 쉬운 문제입니다. 얼핏 보면 원래 list의 K번째의 index를 기억해 놓은 후에 list를 정렬하고 해당 index가 몇번째에 위치하는지를 알아내면 될 것 같이 보입니다. 물론 그것이 정답을 구해낼 수는 있습니다. 하지만 정렬하는데에 $O(n\log n)$의 complexity가 들게 됩니다.
반면, 이것을 $O(n)$의 complexity로 구해내는 방법은 없을까요? 우리가 필요한 것은 어느 특정 한 곡의 위치이지 정렬된 playlist전체를 원하지는 않습니다. 따라서 이 점을 이용하면 더 좋은 방법으로 답을 구해낼 수 있습니다. 이 방법은 바로, 현재 리스트에서 K번째의 index를 안 뒤에 전체 리스트를 돌면서 K보다 작은 index들을 count합니다. 그렇게 되면 그 count가 정렬된 후의 제가 제일 좋아하는 노래의 위치가 될 것입니다.
이를 코드를 통해 구현해 보겠습니다.
def findSongPos(A, K):
original_pos = A[K-1]
count = 1 #해당 곡이 가장 번호가 작으면 첫번째에 있을 거니까요 :)
#list를 루프 돌면서 해당 곡보다 번호가 작은 노래가 몇개인지 count합니다.
for i in A:
if i < original_pos:
count += 1
return count
>>> print findSongPos([1,3,4,2], 2)
3
>>> print findSongPos([1,2,3,9,4], 5)
4
>>> print findSongPos([1,2,3,9,4], 1)
1어떻게 하면 Complexity를 더 줄일 수 있는지 연습할 수 있는 좋은 예제였습니다 :)