문제 설명
소문자 알파벳과 '?' 문자로만 이루어진 문자열 s가 있다고 가정해 보겠습니다. 이때 모든 '?'를 소문자 알파벳으로 바꿔서, 최종 문자열에는 같은 문자가 연속해서 나타나지 않도록 만들어야 합니다. 조건을 만족하는 답이 여러 개라면 그중 무엇을 반환해도 괜찮습니다.
예를 들어 입력이 s = "hel??"라면 출력은 "helab"이 될 수 있습니다. 첫 번째 물음표는 바로 앞의 'l'과만 다르면 되고, 그 자리가 정해진 뒤에는 두 번째 물음표가 새로 생긴 앞 문자와만 다르면 되기 때문입니다.
접근 방법: 그리디로 한 글자씩 채우기
이 문제는 그리디(greedy) 기법으로 아주 단순하게 해결할 수 있습니다. 문자열을 왼쪽에서 오른쪽으로 훑으면서 각 '?' 자리에 다음 규칙을 적용합니다.
- 양옆 확인: '?' 위치의 왼쪽 문자와 오른쪽 문자를 살펴봅니다. 문자열의 맨 앞이나 맨 끝이라면 존재하는 한쪽만 확인하면 됩니다.
- a, b, c 순서로 시도: 'a'부터 'c'까지 차례로 대입해 보고, 양옆 문자와 겹치지 않는 첫 번째 후보를 선택합니다.
- 안전성: 왼쪽에서 오른쪽 순서로 처리하므로 왼쪽 이웃은 이미 확정된 값입니다. 오른쪽 이웃이 아직 '?'라면 당장은 제약이 없고, 나중에 그 자리를 채울 때 현재 값을 피하도록 처리되므로 충돌이 발생하지 않습니다.
알파벳은 총 26글자이므로, 인접한 두 문자가 많아야 2개의 후보만 막을 수 있습니다. 따라서 'a', 'b', 'c' 세 글자만 시험해 보면 반드시 사용 가능한 문자가 남습니다. 참고로 문자열 전체가 "?" 하나뿐인 경우에도 이 로직이 자연스럽게 "a"를 반환하므로 별도의 예외 처리가 필요하지 않습니다.
파이썬 구현 예제
다음 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(s):
s = list(s)
for i in range(len(s)):
if s[i] == '?':
for c in 'abc':
left_ok = (i == 0) or (s[i - 1] != c)
right_ok = (i == len(s) - 1) or (s[i + 1] != c)
if left_ok and right_ok:
s[i] = c
break
return ''.join(s)
s = 'hel??'
print(solve(s))
실행 결과
입력
"hel??"
출력
helab
코드 동작 원리
- 먼저 문자열을 리스트로 변환해 각 자리를 자유롭게 수정할 수 있도록 준비합니다.
- 모든 인덱스를 순회하면서 값이 '?'인 자리만 처리합니다.
- left_ok는 왼쪽 이웃과 겹치지 않는지, right_ok는 오른쪽 이웃과 겹치지 않는지를 나타냅니다. 맨 앞(i == 0)이나 맨 끝(i == len(s) - 1)에서는 해당 방향의 검사를 건너뜁니다.
- 두 조건을 모두 만족하는 첫 번째 후보를 해당 자리에 넣고, break로 내부 반복을 즉시 종료합니다.
- 모든 자리가 채워지면 join()으로 문자열을 합쳐 반환합니다.
복잡도 분석
각 '?'마다 최대 3개의 후보 문자만 확인하므로 전체 시간 복잡도는 O(n)입니다. 문자열을 리스트로 변환하고 다시 합치는 과정에서 O(n)의 추가 공간이 사용됩니다.