문제 정의
영어 소문자 알파벳과 물음표("?")로 구성된 문자열 s가 주어졌다고 가정해 보겠습니다. 각 물음표는 제거하거나 임의의 소문자로 대체할 수 있습니다. 이때 문자 'a'로 시작하면서 알파벳 순서대로 연속적으로 증가하는 부분 문자열 중 가장 긴 것의 길이를 구해야 합니다.
예를 들어 입력 문자열이 s = "vta???defke"라면 정답은 6입니다. 물음표 세 개를 'b', 'c', 'd'로 바꾸면 문자열이 "vtabcdefke"가 되는데, 여기서 "abcdef"가 'a'로 시작하는 가장 긴 연속 증가 부분 문자열이기 때문입니다.
접근 방법
이 문제는 문자열을 한 번만 순회하는 O(n) 선형 시간 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 물음표가 어떤 문자로든 변신할 수 있다는 점을 활용하는 것입니다. 순회 과정에서 다음 두 값을 관리합니다.
- length: 현재 위치까지 완성된 연속 증가 수열의 길이
- qmarks: 직전까지 연속해서 등장한 물음표의 개수
알파벳 문자 c를 만났을 때, c의 알파벳 인덱스(idx = ord(c) - ord('a'))가 현재 수열과 물음표 개수로 커버 가능한 범위 안에 있다면 수열을 이어갈 수 있습니다. 조건은 다음과 같습니다.
length <= idx <= length + qmarks: 지금까지의 수열 뒤에 물음표를 적절히 채워 c까지 이어 붙일 수 있는 경우idx <= qmarks: 앞선 물음표들을 'a'부터 차례로 채워 새로운 수열을 시작할 수 있는 경우
두 조건 중 하나라도 만족하면 length를 idx + 1로 갱신하고, 그렇지 않으면 0으로 초기화합니다. 물음표를 만나면 qmarks를 1씩 늘립니다. 매 단계마다 답의 후보는 min(length + qmarks, 26)이 됩니다. 뒤따르는 물음표들이 수열을 전체 알파벳 개수인 26까지 확장할 수 있기 때문입니다.
풀이 절차
- maxlen, length, qmarks를 모두 0으로 초기화합니다.
- 문자열 s의 각 문자 c에 대해 반복합니다.
- c가 "?"라면 qmarks를 1 증가시킵니다.
- 그렇지 않다면 idx를 계산하고, 위 조건에 따라 length를 갱신한 뒤 qmarks를 0으로 되돌립니다.
- maxlen을 maxlen과 min(length + qmarks, 26) 중 더 큰 값으로 갱신합니다.
- 반복이 끝나면 maxlen을 반환합니다.
파이썬 구현 코드
더 나은 이해를 위해 아래 구현 예제를 살펴보겠습니다.
def solve(s):
maxlen = length = qmarks = 0
for c in s:
if c == "?":
qmarks += 1
else:
idx = ord(c) - ord("a")
length = idx + 1 if length <= idx <= length + qmarks or idx <= qmarks else 0
qmarks = 0
maxlen = max(maxlen, min(length + qmarks, 26))
return maxlen
s = "vta???defke"
print(solve(s))
실행 결과
입력:
"vta???defke"
출력:
6
마무리
이 풀이의 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다. 문자열을 한 번만 훑으면서 현재 증가 수열의 길이와 사용 가능한 물음표 개수만 추적하면 되기 때문에 매우 효율적이며, 길이가 긴 문자열에서도 안정적으로 동작합니다.