[SW Expert Academy] 20936. 상자 정렬하기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AY9QUhl6cfQDFAVF

SW Expert Academy

비어있는 자리(X)로 상자들을 이동하면서, 정렬하는 문제이다!

 

 

🎁 풀이

처음에 어떤 순서로 옮겨야할지 고민했는데, " 이러한 방법을 아무거나 하나 구하는 프로그램" 으로 명시되어있어서,

왼쪽부터 정렬되지 않은 첫번째 상자를 X로 바꾼후, 그 자리를 sort하는 식으로 풀었다. 

T=int(input())
for _ in range(T):
    N=int(input())
    n_list=list(map(int,input().split()))
    correct=sorted(n_list)
    n_list.append('X')
    x_index_log=[] # X의 자리를 담을 리스트
    sort_index=0
    while n_list[:N]!=correct: # 정렬이 완료되었는지 확인
        x_index=n_list.index('X')
        if x_index==N: # X가 가장 끝에있다면, 최초로 정렬이 안되어있는 위치와 자리를 바꿈
            for i in range(N):
                if n_list[i]!=i+1:
                    change_index=i
                    break
            temp=n_list[change_index]
            n_list[change_index]='X'
            n_list[-1]=temp
            x_index_log.append(change_index+1)
            continue
        
        x_index_log.append(n_list.index(x_index+1)+1) # X의 인덱스의 위치에 그에 맞는 상자를 옮김

        n_list[n_list.index(x_index+1)]='X'
        n_list[x_index]=x_index+1
        
    print(len(x_index_log))
    print(' '.join(map(str,x_index_log)))