단조 증가 문자열(Monotonically Increasing String)이란?
'0'과 '1'로만 이루어진 이진 문자열이 단조 증가(monotonically increasing) 상태라는 것은, 앞쪽에 일정 개수의 '0'(0개일 수도 있음)이 배치되고 그 뒤를 일정 개수의 '1'(역시 0개일 수도 있음)이 따르는 형태임을 의미합니다. 예를 들어 '00111', '0000', '1111'은 모두 단조 증가 문자열입니다.
문제 정의
이진 문자열 str을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
문자열 안에서 임의의 '0'을 '1'로, 또는 '1'을 '0'으로 자유롭게 뒤집을 수 있습니다. 이때 함수는 문자열 전체를 단조 증가 상태로 만들기 위해 필요한 최소 뒤집기 횟수를 반환해야 합니다.
예를 들어 함수의 입력이 다음과 같다면:
입력
const str = '00110';
출력
const output = 1;
출력 설명
마지막에 있는 '0'을 '1'로 한 번만 뒤집으면 문자열이 '00111'이 되어 단조 증가 조건을 만족하기 때문입니다.
접근 방식: 메모이제이션을 활용한 재귀 탐색
이 문제는 각 위치에서 두 가지 선택지(현재 문자를 그대로 두거나 뒤집는 것)를 고려해야 하므로, 완전 탐색만으로는 비효율적입니다. 대신 동적 계획법(DP)과 메모이제이션을 결합하면 중복 계산을 제거하고 O(n) 수준의 시간 복잡도로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다:
helper(index, prev): index 위치부터 문자열 끝까지 처리할 때, 직전 문자가prev였다고 가정하고 필요한 최소 뒤집기 횟수를 반환합니다.- 직전 문자가 '0'이었다면, 현재 문자를 '0'으로 유지할지 '1'로 바꿀지 두 경우를 모두 시도한 뒤 더 작은 값을 선택합니다.
- 직전 문자가 이미 '1'이라면, 단조 증가 조건상 이후의 모든 문자는 반드시 '1'이어야 하므로 선택의 여지가 없습니다.
map객체에 각 (index, prev) 조합의 결과를 캐싱하여 동일한 하위 문제의 반복 계산을 방지합니다.
구현 예제
const str = '00110';
const countFlips = (str = '') => {
const map = {}
const helper = (index, prev) => {
map[index] = map[index] || {}
if (map[index][prev] !== undefined) {
return map[index][prev]
}
if (index >= str.length) {
return 0
}
if (prev === '0') {
if (str[index] === '0') {
map[index][prev] = Math.min(helper(index + 1, '0'), helper(index + 1, '1') + 1)
} else {
map[index][prev] = Math.min(helper(index + 1, '1'), helper(index + 1, '0') + 1)
}
} else if (str[index] === '0') {
map[index][prev] = helper(index + 1, '1') + 1
} else {
map[index][prev] = helper(index + 1, '1')
}
return map[index][prev]
}
return helper(0, '0')
};
console.log(countFlips(str));실행 결과
1
동작 과정 살펴보기
입력 문자열 '00110'의 경우, 함수는 처음부터 순차적으로 각 위치를 검사합니다. 네 번째 문자 '1'까지는 뒤집기 없이 진행할 수 있지만, 마지막 '0'은 앞서 '1'이 등장했으므로 반드시 '1'로 뒤집어야 합니다. 결과적으로 총 1번의 뒤집기로 '00111'이라는 단조 증가 문자열을 얻게 됩니다.
이처럼 메모이제이션 기반 재귀를 활용하면 문자열의 길이가 길어져도 각 상태를 한 번씩만 계산하므로 효율적으로 최소 뒤집기 횟수를 구할 수 있습니다.