[ BOJ ] 20127 : Y-수열 ( GOLD 5 ) / Python

문제

N개의 정수로 이루어진 수열 a1, ... , aN이 있다. 택희는 해당 수열이 증가수열 혹은 감소수열이 되게 만들고 싶다.

증가수열은 모든 i(1 ≤ i < N)에 대해서 ai ≤ ai+1을 만족하는 수열이고, 감소수열은 ai ≥ ai+1을 만족하는 수열이다.

택희는 해당 수열의 맨 앞의 k개의 원소를 맨 뒤로 옮겨서 증가수열 또는 감소수열을 만들고 싶다. 즉, ak+1, ..., aN, a1, ..., ak가 증가수열, 또는 감소수열이 돼야 한다. 옮기지 않는 경우는 k=0이라고 하자. 이때, 적절한 k를 골라서 원하는 수열을 만들 수 있게 도와줘라.

입력

다음과 같이 입력이 주어진다.

N
a1 . . . aN

출력

증가수열, 또는 감소수열을 만들 수 있는 k를 출력하여라. 가능한 k가 여러 개면 가능한 가장 작은 k를 출력하여라. 만약에 그런 k가 존재하지 않는다면 -1을 출력하여라.

풀이 과정

먼저, 주어진 수열이 이미 증가수열이거나 감소수열이라면 0을 출력한다.

 

증가수열을 만들 수 있는지 보기 위해, 수열에서 증가하는 부분끼리 나누어 만약 나누어진 부분이 두 부분이면서 나누어진 부분의 앞 부분의 첫 번째 수가 나누어진 부분의 뒷 부분의 마지막 번째 수보다 크거나 같으면 증가수열을 만들 수 있다. (ex 4 5 / 1 2 3 ) 

감소수열을 만들 수 있는지 보기 위해, 수열에서 감소하는 부분끼리 나누어 만약 나누어진 부분이 두 부분이면서 나누어진 부분의 앞 부분의 첫 번째 수가 나누어진 부분의 뒷 부분의 마지막 번째 수보다 작거나 같으면 감소수열을 만들 수 있다. (ex 3 2 1 / 5 4 )

 

증가수열이나 감소수열을 만들 수 있다면, 맨 앞 k 개의 원소를 맨 뒤로 옮겨야 하므로 나누어진 부분의 앞 부분의 길이를 출력한다.

증가수열도 만들 수 있고 감소수열도 만들 수 있는 상황이 존재할 수 있으므로, 이에 대한 예외처리도 진행한다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))
if list(sorted(arr)) == arr or list(sorted(arr))[::-1] == arr: print(0)
else:
    up = [[arr[0]]]

    for i in range(1, n):
        if arr[i-1] > arr[i]: 
            up.append([])
        up[-1].append(arr[i])

    down = [[arr[0]]]

    for i in range(1, n):
        if arr[i-1] < arr[i]: 
            down.append([])
        down[-1].append(arr[i])

    if len(up) == 2 and up[-1][-1] <= up[0][0]: 
        if len(down) == 2 and up[-1][-1] >= up[0][0]:
            print(min(len(up[0]), len(down[0])))
        else:
            print(len(up[0]))
    elif len(down) == 2 and up[-1][-1] >= up[0][0]: print(len(down[0]))
    else: print(-1)