[python] algospot SORTGAME

문제

-> 문제 링크 : https://algospot.com/judge/problem/read/SORTGAME

algospot.com :: SORTGAME

 

문제풀이

문제에서 입력값으로 들어오는 최대 수열의 길이가 8이다.

이떄 만들어질 수 있는 모든 경우의 수는 8! = 4만이다.

가능한 경우의 수가 작기 떄문에 BFS를 통해 문제를 해결할 수 있다. (시간복잡도는?)

 

모든 가능한 수열을 정점으로 하고 뒤집는 연산을 통해 만들어질 수 있는 수열들은 간선으로 이어 그래프를 만들었을 때,

이런 그래프를 바탕으로 BFS를 돌리게 되면 몇번의 뒤집기 연산만에 수열 A에서 수열 B로 변환되는지 알 수 있다.

 

하지만 테스트케이스가 50건이라 새로운 수열이 들어올 때마다 매번 계산하기에는 시간이 너무 오래 걸린다.

그렇기에 만들어질 수 있는 모든 수열에 대해 몇 번의 뒤집기 연산만에 정렬된 수열이 되는지 계산해 놓은 뒤 해당 수열이 들어오면 답을 반환하는 방법을 사용했다.

 

어떤 수열을 정렬시키는 최소 횟수는 정렬된 수열을 어떤 수열로 만드는 최소 횟수와 같다.

모든 경우의 수를 찾는 방법은 정답에서 시작해 BFS를 통해 모든 경우의 수에 해당하는 최소 횟수를 구할 수 있다.

 

이때 "4132"를 정렬하는 최소 횟수는 "41325678"을 정렬하는 최소 횟수와 같다.

즉 어떤 수열이 들어왔을 때 길이가 8이 안된다면 뒷 부분은 정렬된 수를 넣어 길이를 8로 맞춰준 뒤 최소 횟수를 구하면 된다.

그러므로 최대 길이를 이용해 모든 수열의 최소 횟수를 만들어 놓으면 길이가 짧은 수열이 들어와도 사용할 수 있다.

 

BFS 함수에서는 반복문을 통해 큐에 값이 있다면 계속해서 돌아가게 된다.

현재 수열에서 만들 수 있는 모든 수열 중 아직 만들어지지 않았던 수열을 모두 큐에 넣고 반복한다.

 

코드

import sys
from collections import deque

def bfs(start, length) :

    queue = deque()
    queue.append((start,0))
    dp['12345678'] = 0

    while queue :
        now, level = queue.popleft()

        for i in range(len(now)) :
            for j in range(i+1,len(now)) :
                now[i:j+1] = now[i:j+1][::-1]
                string = "".join(now)

                if dp.get(string) is None :
                    queue.append((list(now),level+1))
                    dp[string] = level+1

                now[i:j + 1] = now[i:j + 1][::-1]


T = int(sys.stdin.readline().rstrip())
dp = {}

array = [str(num+1) for num in range(8)]
bfs(array, len(array))

for _ in range(T) :

    N = int(sys.stdin.readline().rstrip())
    array = list(map(int, sys.stdin.readline().rstrip().split()))

    sorted_arr = list(sorted(array))
    mapped = dict(zip(sorted_arr, range(1,N+1)))

    array = [mapped[num] for num in array]
    array = array + [num+1 for num in range(len(array), 8)]
    key = "".join(map(str,array))
    print(dp[key])

초기 접근 방식과 오답의 원인

알고스팟에서는 파이썬 코드로는 시간초과가 난다.

 

 

코드에 잘못된 부분이나 개선 사항을 댓글로 알려주시면 감사하겠습니다.