백준 / python / 1327. 소트 게임

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

 

문제 요약

수의 배열에 대해 K 개의 연속한 숫자를 역순으로 만드는 연산을 수행할 수 있을때,

최소 몇 번의 연산을 거치면 수가 오름차순으로 배열되는지 구하라

 

 

풀이 요약

1. bfs 로 가능한 모든 가능성을 탐색하면서 이미 탐색한 경우 건너뛴다.

2. queue 에 지금의 숫자 배열과 함께 그 배열이 나오기까지 몇 번의 연산을 수행했는지 기록한다.

3. pop 했을때 나온 숫자 배열이 오름차순인 경우, 그 숫자 배열과 함께 저장된 연산 횟수를 출력한다.

 

주의사항

1. 메모리 초과를 신경써야한다.

특히 visited[next] = True 를 q.append() 직후에 해야한다.

그렇게 해야 중복된 값이 다시 큐에 들어가지 않아서 큐의 크기가 최소화된다.

 

2. 그리고 당연하게 생각할 수 있지만 visited 는 배열이 아니라 dictionary 로 만들어야 한다.

배열로 만들게되면 불필요한 공간이 할당되어 메모리가 초과될 수 있다.

 

3. reversed 메소드는 [::-1] 에 비해 느리다. 실행시간이 100ms 이상 차이난다.

 

from sys import stdin
from collections import deque

input = stdin.readline

N, K = map(int, input().split())
numbers = "".join(input().split())


visited = {}
visited[numbers] = True

sorted_numbers = "".join(sorted(numbers))

q = deque([[numbers, 0]])
ans = -1

while q:
    target, iter = q.popleft()

    if target == sorted_numbers:
        ans = iter
        break

    for i in range(N - K + 1):
        next = target[0:i] + target[i : i + K][::-1] + target[i + K :]

        if next in visited:
            continue

        q.append([next, iter + 1])
        visited[next] = True

print(ans)