20127번: Y-수열 (구현)

20127번: Y-수열

반례를 스스로 생각하고 다양한 경우를 고려하면서 코딩하는 것이 중요한 구현문제이다. 

처음에 단순히 슬라이싱으로 풀면 쉬울 것 같아서 정말로 0 개부터해서 n개까지 slicing해서 뒤로 붙여서 증가수열인지 감소수열인지 확인을 했는데 이러면 시간초과가 뜬다.

아마 슬라이싱을 너무 많이 한 것이 문제가 아닐까 싶어서 최소한 1개는 옮긴다는 가정하에 arr[i-1] > arr[i] 가 나올 때까지를 k를 1부터 증가시키고 arr[i-1] < arr[i] 가 나올때까지 m을 1부터 증가시킨다. k와 m에 대해 각각 슬라이싱을 하고 그 결과가 오름차순이거나 내림차순이면 k 혹은 m을 반환하자는 것이 처음 아이디어였다. 처음 리스트를 arr라고 하면 k혹은 m 만큼 슬라이싱한 결과가 sorted(arr) 혹은 sorted(arr,reverse=True) 와 같은지 확인하는 것이다.

이때 만약 둘다 만족하는 경우가 있을 수 있다. 예를 들어서 [1 2 1 1 1] 은 k로는 2이고 m으로는 1이다. k는 오름차순을 만드는 애고 m은 내림차순을 만들기 위함이므로 당연하다. 하지만 결과로는 최솟값을 반환해야 하므로 오름차순도 될 수 있고 내림차순도 될 수 있는 것은 작은 값을 반환하기로 하고 그렇지 않은 경우에는 가능한 경우만 반환해야 한다. 여기까지 까먹은 것이 아무것도 움직이지 않을 때가 있다. 이때는 처음부터 이미 오름차순 혹은 내림차순을 만족하는 경우이다.  

n = int(input())
arr = list(map(int,input().split()))
def solve():
    k,m = 1,1
    for i in range(1,n):
        if arr[i-1] > arr[i]:
            break
        k += 1
    for i in range(1,n):
        if arr[i-1] < arr[i]:
            break
        m += 1
    arr1 = sorted(arr)
    arr2 = sorted(arr,reverse=True)
    if (arr == arr1 or arr == arr2):
        print(0)
    elif arr[k:] + arr[:k] == arr1 and arr[m:] + arr[:m] == arr2 :
        print(min(k,m))
    elif arr[k:] + arr[:k] == arr1:
        print(k)
    elif arr[m:] + arr[:m] == arr2:
        print(m)
    else:
        print(-1)
solve()