[백준]1327 소트게임

1. 풀이

(1) bfs를 돌리려다 8자리 숫자를 visited처리해주기 위해서 100000000개의 리스트를 만들었다. 하지만 메모리초과. (4*100000000byte=390625KB=381MB)

 

(2) 이후 수학&그리디로 풀려고 시도했지만 규칙 못찾음

 

(3) visited를 set으로 관리하면 됨.

​

* visited를 무조건(0 or 1) 값을 갖는 리스트로만 생각하지말고 set or dictionary도 생각해줄것!

​

2. 소스코드

from collections import deque

N,K=map(int,input().split())
L=list(input().split())


visitedS=set("".join(L))
q=deque([["".join(L),0]])

ans=-1
while(q):
    word,cnt=q.popleft()
    tempL=list(word)
    #print(tempL,cnt)

    # 오름차순이면 그만
    if tempL==sorted(tempL):
        ans=cnt
        break

    isFirst=False
    # i를 뒤집기
    for i in range(N-K+1):
        newL = list(tempL)
        targetL=newL[i:i+K]
        targetL.reverse()
        for j in range(K):
            newL[i+j]=targetL[j]
        newWord="".join(newL)
        if newWord not in visitedS:
            visitedS.add(newWord)
            q.append([newWord,cnt+1])

print(ans)