파이썬 DI 문자열 일치(DI String Match) – 그리디 알고리즘으로 손쉽게 풀기

문제 소개

DI 문자열 일치(DI String Match)는 'I'(증가, Increase)와 'D'(감소, Decrease)로만 구성된 문자열 S가 주어졌을 때, 특정 조건을 만족하는 순열을 찾는 대표적인 그리디 알고리즘 문제입니다. 여기서 N은 문자열 S의 길이를 의미합니다.

우리는 [0, 1, ..., N]의 숫자를 모두 한 번씩 사용해 만든 순열 A를 반환해야 하며, 이 순열은 다음 조건을 만족해야 합니다.

• S[i]가 'I'라면 → A[i] < A[i+1], 즉 다음 값이 반드시 더 커야 합니다.
• S[i]가 'D'라면 → A[i] > A[i+1], 즉 다음 값이 반드시 더 작아야 합니다.

예를 들어 입력이 "IDID"라면 출력은 [0, 4, 1, 3, 2]입니다. 실제로 0 < 4, 4 > 1, 1 < 3, 3 > 2로 모든 조건이 순서대로 충족됩니다.

핵심 아이디어: 그리디(Greedy) 접근법

이 문제는 매 순간 최선의 선택을 하는 그리디 기법으로 간단히 해결할 수 있습니다. 핵심 원리는 다음과 같습니다.

• 'I'를 만나면 남은 숫자 중 가장 작은 값을 선택합니다. 최솟값을 미리 소진해 두면, 이후 어떤 숫자를 배치하더라도 반드시 더 큰 값이 되므로 다음 조건을 안전하게 만족할 수 있습니다.
• 'D'를 만나면 남은 숫자 중 가장 큰 값을 선택합니다. 최댓값을 먼저 사용하면 이후 어떤 숫자가 와도 반드시 더 작아지므로 역시 안전합니다.
• 모든 문자를 처리한 뒤 마지막에 남은 숫자 하나를 결과에 덧붙이면 순열이 완성됩니다.

단계별 풀이 과정

1. A := 0부터 N까지의 숫자를 담은 리스트를 생성합니다. (N은 S의 길이)
2. res := 결과를 저장할 빈 리스트를 준비합니다.
3. S의 각 문자 j에 대해 반복합니다.
   • j가 'I'이면 → A의 첫 번째 원소(최솟값)를 꺼내 res에 추가합니다.
   • j가 'D'이면 → A의 마지막 원소(최댓값)를 꺼내 res에 추가합니다.
4. 반복이 끝나면 A에 남아 있는 마지막 숫자를 res에 추가한 뒤 반환합니다.

"IDID" 입력에 대한 동작 추적

파이썬 구현 코드

class Solution:
    def diStringMatch(self, S):
        A = [i for i in range(len(S) + 1)]
        return [A.pop((j == 'I') - 1) for j in S] + A

ob = Solution()
print(ob.diStringMatch("IDID"))

이 코드의 백미는 리스트 컴프리헨션 한 줄입니다. 파이썬에서 비교 연산 (j == 'I')은 True/False, 즉 1/0으로 평가되므로 (j == 'I') - 1은 'I'일 때 0, 'D'일 때 -1이 됩니다. 따라서 pop(0)은 최솟값을, pop(-1)은 최댓값을 꺼내게 됩니다.

실행 결과

입력:

"IDID"

출력:

[0, 4, 1, 3, 2]

복잡도 분석 및 최적화 팁

문자열의 길이를 N이라 할 때, 각 문자마다 한 번의 선택 연산이 수행되므로 전체 시간 복잡도는 O(N)입니다. 공간 복잡도 역시 결과 배열 때문에 O(N)입니다.

다만 파이썬 리스트의 pop(0)은 내부적으로 앞쪽 요소들을 한 칸씩 이동시키므로 최악의 경우 추가 비용이 발생할 수 있습니다. 성능이 중요한 환경에서는 collections.deque를 사용하거나, low·high 두 포인터를 활용해 양 끝 값을 바로 선택하는 방식으로 개선할 수 있습니다.

마무리

DI 문자열 일치 문제는 "증가에는 최솟값, 감소에는 최댓값"이라는 직관적인 그리디 전략만 기억하면 누구나 짧은 코드로 해결할 수 있습니다. 두 포인터 기법과 함께 익혀 두면 코딩 테스트에서 변형 문제를 만나더라도 빠르게 적용할 수 있을 것입니다.