정수들이 섞여있는 수열에서 연속하는 정수 수열을 O(N)에 분리하기

11232번: Shuffles (acmicpc.net)  주어진 수열이 최소 몇번의 shuffle로 이루어진 수열인지 구하는 문제 셔플방법은 수열에서 어떤 특정 지점에서 두 부분으로 나누고 두 부분을 순서를 유지한채 섞는 것이다. 1 2 3 4 5라면..  1 2 3 4 5로 나누고  1 4 2 5 3 처럼 섞는 것 주어진 수열에서 어떤 특정 지점 k에서 나뉘었다고 한다면, 2개의 부분 수열 1,2,3,...,k k+1,k+2,...,n으로 나뉘고 이것이 섞일 것이다. 이렇게 섞인 수열에서 또 한번 나누면 최대 4개의 부분 수열 1,2,3,..,k1 k1,k1+1,...k k+1,k+2,..k2 k2+1,k2+2,...,n으로 구해진다. 여기서 또 한번 나누면 최대 8개의 부분 수열을 얻을 수 있다. ...