정수들이 섞여있는 수열에서 연속하는 정수 수열을 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개의 부분 수열을 얻을 수 있다.

 

....

 

이런 식으로 y번 shuffle했다면 최대 2^y개의 부분 수열을 얻을 수 있다.

 

예를 들어 1,2,3,4,5,6에 대해 생각해보면

 

1,2,3

 

4,5,6으로 나누고

 

1,4,2,5,3,6으로 섞은 다음

 

1,4,2

 

5,3,6에서

 

1,5,4,3,2,6으로 섞으면

 

1 2345 6으로 4개의 부분 수열을 얻는다

 

어떻게 섞느냐에 따라 이보다 더 적은 부분 수열을 가질 수 있는데

 

1,2,34,5,6으로 나눈 다음

 

1,2,4,3,5,6으로 섞고 다시

 

1,2,43,5,6으로 나눈 다음

 

1,3,2,4,5,6으로 섞으면

 

1 23 4 5 6으로 2개의 부분 수열만 나온다

 

----------------------------------------------------------------------------------------------------------------------------------

 

어쨌든 먼저 주어진 수열에서 연속하는 부분 수열이 몇개인지 찾아야한다

 

그 개수가 x개이고 y번 섞었다고 한다면, $x <= 2^{y}$를 만족시키는 y를 구하면 된다.

 

예를 들어

 

1 2 7 3 8 9 4 5 10 6은

 

1,2,3,4,5,6

 

7,8,9,10으로 2개 있다.

 

그래서 1번 섞은 것이다.

 

3 8 1 9 4 5 2 7 10 6은

 

1 23 4 5 678 9 10으로 4개 있다.

 

그래서 2번 섞었다.

 

2 1 4 3 6 5 8 7은

 

12 34 56 78로 5개 있다.

 

그래서 3번 섞었다고 할 수 있다.

 

이걸 어떻게 찾을 수 있을까? $O(N^{2})$말고 생각나는게 없는데...

 

--------------------------------------------------------------------------------------------------------------------------------------------------

 

배열을 순회하면서 현재 A[i]가 아직 방문하지 않았다면, 이것이 새로운 부분 수열의 시작점이고, A[i],A[i]+1을 방문표시 해준다.

 

A[i]가 방문되어 있다면 이미 이전에 부분수열이 있고 A[i]+1을 방문표시 해준다.

 

핵심은 A[i]+1에 방문표시를 해두는 것

 

예를 들어 2,1,4,3,6,5,8,7의 경우

 

먼저 2는 아직 방문하지 않았으므로, 부분 수열의 개수 + 1해주고, 2,3을 방문표시 해준다.

 

2 다음에 3이 나올 것이라고 예상되기 때문이다.

 

그래서 3이 나온다면 이전에 있는 부분 수열의 뒤에 나올 것이기 때문에 미리 표시를 해둔다.

 

다음 1은 아직 방문하지 않았으므로 부분 수열의 개수 + 1해주고, 1,2를 방문표시 해준다.

 

현재 

 

2,31 로 2개 찾은 것

 

다시 4가 나온다면 아직 방문하지 않았으므로 부분 수열의 개수 + 1 해주고, 4,5 방문표시 해준다

 

2,314,5로 3개 찾은 것

 

다음 3은 방문표시 되어있으니 4에 방문표시를 해주고 넘어가고 6이 나온다면?

 

아직 방문하지 않았으므로 부분 수열의 개수 +1 해주고 6,7 방문표시 해준다

 

2,314,56,7로 4개 찾았다.

 

5는 방문표시 되었으니 6에 방문표시 해주고 넘어가고

 

8은 아직 방문하지 않았으니 부분 수열의 개수 +1 해주고 8,9 방문표시 해준다

 

2,314,56,78,9로 5개 찾았다.

 

9는 실제로 없지만 알고리즘을 위해 넣어준 것이고, 다음 7은 이미 방문표시 되어있으니 8에 방문표시 해주고 넘어간다.

 

n = int(input())

A = list(map(int,input().split()))

visited = [0]*(n+2)

#연속하는 부분 수열의 개수
count = 0

for i in range(n):
    
    if visited[A[i]] == 0:
        
        count += 1
        visited[A[i]] = 1
    
    visited[A[i]+1] = 1


#2^y >= count인 y가 셔플 횟수
v = 1
y = 0

while v < count:
    
    v *= 2
    y += 1

print(y)