[문제출처 : Codechef] 이번에 풀어볼 문제는 Permutation에 관한 문제입니다. Permutation은 주어진 리스트를 나열하는 순서라고 보실 수 있는데요, 예를 들면, permutation list가 [1, 4, 2, 3] 이렇게 있다면 이 의미는 숫자 1이 첫번째에 있고, 숫자 2가 네번째에 있고, 숫자 3이 두번째, 숫자 4가 세번째에 있는 리스트라는 얘기로써, 이를 복원한 inverse permutation은 [1, 3, 4, 2]가 됩니다.
그런데 때로는 permutation을 복원한 inverse permutation이 permutation과 동일한 경우도 발생하게 됩니다. 이럴 때 이를 ambiguous permutation이라고 하는데요, 예를 들면 [1, 4, 3, 2]의 permutation은 복원을 해도 [1, 4, 3, 2]가 나오게 되서 이를 ambiguous(애매모호) 하다고 합니다.
자 그럼 먼저 주어진 permutation을 어떻게 복원할 것인지 프로그램으로 구현해 보겠습니다. 제 방법은 주어진 permutation을 루프를 돌면서 해당 index를 그 index의 원소가 가리키는 index로 보내는 방법입니다.
def inversePermutation(A):
InvA = [0]*len(A) #일단 A와 같은 크기의 저장공간을 확보합니다.
for i in range(len(A)): #permutation을 루프를 돌면서,
InvA[A[i]-1] = i+1 #index를 index안의 원소가 가리키는 곳으로 보냅니다.
return InvA잘 동작하는지 확인해 보죠~
>>> print inversePermutation([2,3,4,5,1])
[5, 1, 2, 3, 4]
>>> print inversePermutation([1,4,3,2])
[1, 4, 3, 2]잘 동작하네요 :) 그럼 이제 어떻게 ambiguous인지 아닌지를 판단할까요? 짐작하셨겠지만, 간단하게 두 리스트가 동일한지를 출력하면 됩니다.
def isAmbiguous(A):
return A == inversePermutation(A)
>>> print isAmbiguous([1,4,3,2])
True
>>> print isAmbiguous([2,3,4,5,1])
False
>>> print isAmbiguous([1])
True복잡해 보이는 프로그램도 결국엔 작은 부분부분으로 나눠서 생각하면 훨씬 간단하고 깔끔해 집니다 :)