2026-03-03 문제풀이

35298 책 정렬하기

풀이

연속된 2개를 골라서 맨 앞으로 보내는 연산을 $N^2$ 의 횟수 이내로 정렬을 수행하기만 하면 된다.

target array로 만드는 과정을 생각해보면 맨 뒤를 만들면 그 앞에 배열만 생각하면 된다. 그렇다면 맨 뒤 원소를 차근차근 만들 수 있으면 좋아 보인다.

1 2 3 4 5 -> 주어진 배열을 만든다고 생각해보자. 맨 앞의 2개의 원소를 원하는 곳으로 세트로 보낼 수 있는 상황이다.

예를 들어 문제에 있는1 2 4 5 3을 생각해보자.

1 2 3 4 5 ->
3 4 5 1 2 -> 
5 3 4 1 2 ->
4 1 2 5 3 -> 5, 3을 완성
2 4 1 5 3 ->
1 2 4 5 3 -> 모두 완성

이렇게 원하는 것들을 뒤로 보내다보면 완성이 될 것 같고 세번째 요소까지 뒤로 보내는데 성공했지만 완성되지 않았을 경우 실패할 것 이라고 예상했다.

뒤로 보내고 싶은 요소의 index가 짝수라면 2개씩 빼서 맨뒤로 보내기 수월하다. 하지만 홀수라면 짝수로 바꾸는 과정이 필요하다. 맨 앞으로 보내고 2 3 1에서 2를 2번째로 보내는 과정은 1 2 3으로 바꾸는 것이다. 이 과정을 수행하고 맨 뒤로 보내면 된다.

코드

N = int(input())
A, B, R = [0] + list(map(int, input().split())), [i for i in range(N+1)], []
for i in range(N, 2, -1) : 
    x = B.index(A[i])
    if x == i : continue
    while x > 2 :
        B = B[:1] + B[3:i+1] + B[1:3] + B[i+1:]
        R += [i-1]
        x = B.index(A[i])
    
    if x == 1 : 
        R += [2]
        B = B[:1] + B[3:4] + B[1:3] + B[4:]
        
    B = B[:1] + B[3:i+1] + B[1:3] + B[i+1:]
    R += [i-1]
    

if A[1] != B[1]: 
    print("NO")
else : 
    print("YES")
    print(len(R))
    print(*R[::-1])