파이썬으로 배열에서 엄격한 감소·증가 수열을 이루는 전환점 요소 찾기

문제 개요

양의 정수로 구성된 배열이 하나 주어져 있다고 가정해 보겠습니다. 이 배열 안에서 어느 한 지점(요소)을 기준으로, 그 지점까지는 엄격하게 감소하는(strictly decreasing) 수열이 만들어지고, 그 지점부터는 다시 엄격하게 증가하는(strictly increasing) 수열이 만들어지도록 하는 전환점 요소를 찾아야 합니다.

이 문제를 풀 때 반드시 기억해야 할 조건은 다음과 같습니다.

감소 수열과 증가 수열은 각각 최소 길이 2 이상이어야 합니다.
감소 수열의 마지막 값은 곧 증가 수열의 첫 번째 값이 되며, 두 수열이 이 값을 공유합니다.

예를 들어 입력이 {5, 4, 3, 4}라면 출력은 3입니다. {5, 4, 3}은 엄격하게 감소하는 수열이고, 이어서 {3, 4}는 엄격하게 증가하는 수열을 이루기 때문입니다.

알고리즘 접근 방법

배열을 한 번만 순회하면서 현재 구간이 감소 구간인지 증가 구간인지 추적하면 문제를 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

increase = 1, decrease = 1로 초기화합니다.
n에 배열의 길이를 저장합니다.
i를 1부터 n-1까지 순회하며 다음을 검사합니다.
- array[i] < array[i-1](값이 감소 중)일 때: 아직 증가 구간에 진입하지 않았다면(increase == 1) decrease를 1 증가시키고, 이미 증가 구간에 들어간 상태라면 조건 위반이므로 -1을 반환합니다.
- array[i] > array[i-1](값이 증가 중)일 때: 감소에서 증가로 처음 전환되는 순간이라면(increase == 1) 전환점 pt에 array[i-1]을 저장합니다. 그리고 감소 수열의 길이가 2 이상(decrease >= 2)이면 increase를 1 증가시키고, 그렇지 않으면 -1을 반환합니다.
- array[i] == array[i-1](값이 같음)일 때: '엄격한' 증가·감소 조건에 어긋나므로 -1을 반환합니다.
순회가 끝난 후 increase >= 2이고 decrease >= 2라면 전환점 pt를 반환하고, 그렇지 않으면 -1을 반환합니다.

이 알고리즘은 배열을 한 번만 훑기 때문에 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.

파이썬 구현 예제

def search_element(array):
    increase = 1
    decrease = 1
    n = len(array)
    for i in range(1, n):
        if(array[i] < array[i-1]):
            if increase == 1:
                decrease = decrease + 1
            else:
                return -1
        elif(array[i] > array[i-1]):
            if increase == 1:
                pt = array[i-1]
            if decrease >= 2:
                increase = increase + 1
            else:
                return -1
        elif(array[i] == array[i-1]):
            return -1
    if(increase >= 2 and decrease >= 2):
        return pt
    else:
        return -1

array = [5,4,3,4]
element = search_element(array)
print(element)

입력

[5,4,3,4]

출력

동작 원리 살펴보기

배열 [5, 4, 3, 4]에 대해 코드가 어떻게 작동하는지 단계별로 확인해 보겠습니다.

i=1: 4 < 5 → 감소 구간이므로 decrease = 2
i=2: 3 < 4 → 감소 구간이므로 decrease = 3
i=3: 4 > 3 → 처음 증가로 전환되는 시점이므로 pt = 3, decrease ≥ 2이므로 increase = 2
순회 종료 후 increase = 2, decrease = 3 → 두 조건 모두 만족하므로 pt인 3을 반환

참고로 배열이 계속 감소하기만 하거나 계속 증가하기만 하는 경우에는 감소·증가 두 수열이 모두 존재하지 않으므로 -1이 반환됩니다. 인접한 두 값이 같은 경우 역시 '엄격한' 조건을 만족하지 못해 -1을 반환하게 됩니다.