파이썬으로 단조 증가·감소 문자열 분할의 최소 그룹 개수 구하기

문제 이해하기

소문자로만 이루어진 문자열 s가 주어졌을 때, s를 연속된 부분 문자열들로 나누려고 합니다. 이때 각 부분 문자열은 단조 증가(non-decreasing) 또는 단조 감소(non-increasing) 상태여야 하며, 필요한 최소한의 부분 문자열 개수를 구하는 것이 목표입니다.

예를 들어 "pqqqr"은 단조 증가 문자열이고, "qqqp"는 단조 감소 문자열입니다.

입출력 예시

s = "pqrsrqp"인 경우 출력은 2가 됩니다. 문자열을 "pqrs"(단조 증가)와 "rqp"(단조 감소)라는 두 조각으로 나눌 수 있기 때문입니다.

해결 접근 방법

이 문제는 문자열을 한 번만 순회하는 그리디 방식으로 해결할 수 있습니다. 핵심 아이디어는 인접한 두 문자의 크기 관계를 계속 추적하다가, 정렬 방향이 바뀌는 지점에서 새로운 그룹을 시작하는 것입니다.

구체적인 알고리즘은 다음과 같습니다.

• 문자열이 비어 있으면 0을 반환합니다.
• last(이전 문자)는 첫 번째 문자로, direction(현재 방향)은 1(미정)로, count(그룹 수)는 1로 초기화합니다.
• 문자열의 각 문자를 순회하며 다음 규칙을 적용합니다.
  • 현재 문자가 last보다 큰 경우:
    • direction이 1이면 → direction을 0(증가)으로 변경합니다.
    • direction이 2(감소 중)이면 → 방향 전환이 발생한 것이므로 direction을 1로 되돌리고 count를 1 증가시킵니다.
  • 현재 문자가 last보다 작은 경우:
    • direction이 1이면 → direction을 2(감소)로 변경합니다.
    • direction이 0(증가 중)이면 → 방향 전환이 발생한 것이므로 direction을 1로 되돌리고 count를 1 증가시킵니다.
• 순회가 끝나면 count를 반환합니다.

구현 예제

아래 파이썬 코드를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.

def solve(s):
    if not s:
        return 0

    last = s[0]
    direction = 1
    count = 1

    for char in s:
        if char > last:
            if direction == 1:
                direction = 0
            elif direction == 2:
                direction = 1
                count += 1
        elif char < last:
            if direction == 1:
                direction = 2
            elif direction == 0:
                direction = 1
                count += 1
        last = char

    return count

s = "pqrsrqp"
print(solve(s))

입력

"pqrsrqp"

출력

2

복잡도 분석

문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 매우 긴 문자열에 대해서도 효율적으로 동작합니다.