[백준] 15887번 : 욱제는 결벽증이야!! (Python 파이썬)

알고리즘 분류 : 구현, 정렬, 구성적

https://www.acmicpc.net/problem/15887

15887번: 욱제는 결벽증이야!!

[ 풀이 ]

 이 문제는 주어진 리스트를 정렬하기 위해서 필요한 횟수와 리스트의 어떤 부분을 reverse 하면 되는지 구하는 문제다. 

 이 문제는 리스트가 정렬되기 위해서 최수 횟수를 구하는 게 아니기 때문에 하나씩 그 자리를 맞춰주면 된다.

  예를 들어, [2, 1, 5, 4, 3]을 [1, 2, 3, 4, 5]로 만들기 위해서는 아래의 과정이 필요하다.

 리스트의 첫 번째 칸에 1이 있으면 2로 넘어가고, 1이 없다면 리스트에 1이 있는 칸과 맨 앞의 칸까지의 [2 ,1]을 reverse 해서 [1, 2]로 만든다. 그러면 두 번째 칸에는 2가 있으므로 3으로 넘어가고, 3은 세 번째 칸에 없으므로 [5, 4, 3]을  reverse 해서 [3, 4, 5]로 만든다. 이때 그 두 숫자의 자리만 바꾸는 것이 아니라 그 두 숫자를 앞뒤로 하는 리스트 전체를 reverse 하는 것이다.

 

[ 코드 ]

n=int(input())
a=list(map(int,input().split()))
b=a.copy()
b.sort()
i=1
op=0
ch=[]
while a!=b:
    if a[i-1]!=i:
        op+=1
        k=a.index(i)+1
        a[i-1:a.index(i)+1]=a[i-1:a.index(i)+1][::-1]
        ch.append([i,k])
    i+=1
print(op)
for i in ch: print(*i)

[ 코드 설명 ]

리스트 b에 리스트 a를 복사해서 b는 먼저 정렬을 해놓고 while문으로 원래 리스트 a가 정렬된 리스트 b와 같은 때까지 반복한다. if문을 돌면서 리스트 a에 i-1번째 칸에 i가 없으면 리스트 a에 i가 있는 칸부터 i-1번째 칸까지 reverse를 한다. 그리고 i를 1씩 더해주면서 계속 돌다가 리스트 a가 정렬이 되면 끝이 난다.