문제 설명
'x', 'y', 'z' 세 종류의 문자로만 이루어진 문자열 s가 주어졌을 때, i개의 'x' 문자 뒤에 j개의 'y' 문자, 그리고 그 뒤에 k개의 'z' 문자가 순서대로 이어지는 부분 수열(subsequence)의 개수를 구하는 프로그램을 작성해야 합니다. 단, i, j, k는 모두 1 이상입니다.
예를 들어 입력이 s = "xxyz"라고 가정해 보겠습니다. 이때 출력은 3이 됩니다. 앞쪽의 두 'x' 중 하나를 선택해 만드는 "xyz" 부분 수열이 두 개 있고, 두 'x'를 모두 사용한 "xxyz" 부분 수열이 하나 있기 때문입니다.
풀이 접근 방식
이 문제는 동적 계획법(DP)을 활용하면 문자열을 한 번만 순회하면서 효율적으로 해결할 수 있습니다. 핵심 아이디어는 세 개의 카운터를 유지하는 것입니다.
- x: 지금까지 확인한 범위에서 만들 수 있는 'x'만으로 구성된 부분 수열의 개수
- y: 'x'가 하나 이상 등장한 뒤 'y'가 이어지는 형태(x…xy…y)의 부분 수열 개수
- z: 'x', 'y'에 이어 'z'까지 붙은 최종 목표 형태(x…xy…yz…z)의 부분 수열 개수
새로운 문자를 만났을 때는 기존 부분 수열에 이 문자를 포함시키는 경우와 포함시키지 않는 경우를 모두 고려해야 하므로 기존 값이 2배가 됩니다. 여기에 새 문자 하나만으로 시작되는 경우, 그리고 바로 이전 단계의 부분 수열을 새 문자로 확장하는 경우를 더해 줍니다.
알고리즘 단계
- n := 문자열 s의 길이
- x := 0, y := 0, z := 0 으로 초기화
- i를 0부터 n-1까지 반복합니다.
- s[i]가 'x'라면: x := x * 2 + 1
- s[i]가 'y'라면: y := y * 2 + x
- s[i]가 'z'라면: z := z * 2 + y
- 반복이 끝나면 z를 반환합니다.
예제 코드 (Python)
class Solution:
def solve(self, s):
n = len(s)
x = 0
y = 0
z = 0
for i in range(n):
if s[i] == "x":
x *= 2
x += 1
if s[i] == "y":
y *= 2
y += x
if s[i] == "z":
z *= 2
z += y
return z
ob = Solution()
print(ob.solve("xxyz"))
입력
"xxyz"
출력
3
동작 과정 살펴보기
입력 "xxyz"에 대해 알고리즘이 어떻게 진행되는지 단계별로 확인해 보겠습니다.
- 인덱스 0 ('x'): x = 0 × 2 + 1 = 1
- 인덱스 1 ('x'): x = 1 × 2 + 1 = 3 → 'x' 하나짜리 부분 수열 3개
- 인덱스 2 ('y'): y = 0 × 2 + 3 = 3 → "xy" 형태 부분 수열 3개
- 인덱스 3 ('z'): z = 0 × 2 + 3 = 3 → "xyz" 형태 부분 수열 3개
최종적으로 z = 3이 반환됩니다. 이는 각각 첫 번째 또는 두 번째 'x'를 사용한 "xyz" 두 개와, 두 'x'를 모두 사용한 "xxyz" 하나에 해당합니다.
복잡도 분석
문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 세 개의 변수만 사용하므로 추가 공간 복잡도는 O(1)입니다.