문자열 s가 "1", "2", "3", "?" 네 가지 문자로만 구성되어 있다고 가정해 봅시다. "?" 자리에는 "1", "2", "3" 중 어떤 숫자든 자유롭게 채워 넣을 수 있습니다. 우리가 찾아야 하는 것은 인접한 두 자릿수가 절대 같지 않도록 "?"를 채웠을 때 만들 수 있는 가장 작은 수입니다.
예를 들어 입력이 s = "2??3?"라면, 출력은 21231이 됩니다.
문제 해결 접근 방식
이 문제는 왼쪽부터 차례대로 탐색하면서(greedy 방식) 각 "?" 자리에 가능한 한 작은 숫자를 배치하는 방법으로 해결할 수 있습니다. 각 위치에서 왼쪽과 오른쪽 이웃 숫자를 확인한 뒤, 양쪽 모두와 겹치지 않는 가장 작은 값을 선택합니다.
알고리즘 단계
- i := 0 으로 초기화하고, s를 리스트로 변환합니다.
- 문자열 길이가 2 미만이면서 유일한 문자가 "?"라면 "1"을 반환합니다.
- i가 문자열 길이보다 작은 동안 다음을 반복합니다.
- s[i]가 "?"인 경우:
- 첫 번째 문자(i = 0)라면: 오른쪽 문자가 "1"이 아니면 "1", 그렇지 않으면 "2"를 넣습니다.
- 중간 문자(0 < i < len(s)-1)라면: 왼쪽 문자와 오른쪽 문자를 모두 피하는 가장 작은 숫자를 선택합니다. 예를 들어 왼쪽이 "1"이고 오른쪽이 "2"라면 "3"을, 왼쪽이 "1"이고 오른쪽이 "2"가 아니라면 "2"를 넣습니다.
- 마지막 문자라면: 왼쪽 문자가 "1"이 아니면 "1", 그렇지 않으면 "2"를 넣습니다.
- i를 1 증가시킵니다.
- s[i]가 "?"인 경우:
- 모든 처리가 끝나면 리스트를 문자열로 결합하여 반환합니다.
파이썬 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def solve(s):
i = 0
s = list(s)
if len(s) < 2:
if s[i] == "?":
return "1"
while i < len(s):
if s[i] == "?":
if i == 0:
s[i] = "1" if s[i + 1] != "1" else "2"
elif i > 0 and i <= len(s) - 2:
if s[i - 1] == "1":
if s[i + 1] == "2":
s[i] = "3"
else:
s[i] = "2"
elif s[i - 1] == "2":
if s[i + 1] == "1":
s[i] = "3"
else:
s[i] = "1"
elif s[i - 1] == "3":
if s[i + 1] == "1":
s[i] = "2"
else:
s[i] = "1"
else:
s[i] = "1" if s[i - 1] != "1" else "2"
i += 1
return "".join(s)
s = "2??3?"
print(solve(s))입력
"2??3?"
출력
21231
동작 과정 살펴보기
입력 "2??3?"에 대해 알고리즘이 어떻게 동작하는지 단계별로 확인해 보겠습니다.
- 인덱스 0의 "2"는 이미 확정된 값이므로 그대로 둡니다.
- 인덱스 1의 "?": 왼쪽이 "2"이므로 "1"을 선택합니다. → 현재까지 "21"
- 인덱스 2의 "?": 왼쪽이 "1", 오른쪽이 "3"이므로 "2"를 선택합니다. → 현재까지 "212"
- 인덱스 3의 "3"은 그대로 둡니다.
- 인덱스 4의 "?": 마지막 문자이고 왼쪽이 "3"이므로 "1"을 선택합니다.
최종 결과는 21231이 되며, 어느 위치에서도 인접한 두 숫자가 같지 않음을 확인할 수 있습니다.
시간 복잡도
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가로 사용하는 공간은 문자열을 리스트로 변환하는 데 필요한 O(n)입니다. 따라서 매우 긴 문자열에 대해서도 효율적으로 동작합니다.