문제 설명
두 개의 숫자 문자열 s와 t가 주어집니다. 우리는 다음 연산을 원하는 횟수만큼 반복하여 문자열 s를 t로 변환할 수 있는지 확인해야 합니다.
- s에서 비어 있지 않은 부분 문자열(substring) 하나를 선택합니다.
- 선택한 부분 문자열을 제자리(in-place)에서 오름차순으로 정렬합니다.
예를 들어 입력이 s = "95643", t = "45963"이라면 결과는 True입니다. "95643" → "95463" → "45963"과 같이 변환할 수 있기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 기본값이 리스트인 맵(defaultdict)인 places를 생성합니다.
- i를 문자열 길이 - 1부터 0까지 역순으로 순회하며 다음을 수행합니다.
- key := s[i]를 정수로 변환한 값
- i를 places[key]의 끝에 삽입
- t의 각 문자 e에 대해 다음을 수행합니다.
- key := e를 정수로 변환한 값
- places[key]가 비어 있으면 False를 반환합니다.
- i := places[key]의 마지막 요소(해당 숫자가 나타나는 가장 작은 인덱스)
- j를 0부터 key - 1까지 순회하며 다음을 검사합니다.
- places[j]가 비어 있지 않고 places[j]의 마지막 요소가 i보다 작으면 False를 반환합니다.
- places[key]의 마지막 요소를 삭제합니다.
- 모든 검사를 통과하면 True를 반환합니다.
동작 원리
핵심 아이디어는 t의 왼쪽부터 차례대로 문자를 하나씩 확정하는 것입니다. 특정 자릿수 d를 s의 앞쪽으로 가져오려면 해당 위치를 포함하는 구간을 정렬해야 하는데, 이때 그 구간 안에 d보다 작은 숫자가 아직 남아 있다면 정렬 과정에서 작은 숫자가 먼저 앞으로 오게 됩니다. 따라서 현재 사용하려는 위치보다 앞에 더 작은 미사용 숫자가 존재한다면 변환이 불가능하므로 False를 반환하는 것입니다.
구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
from collections import defaultdict
def solve(s, t):
places = defaultdict(list)
for i in reversed(range(len(s))):
key = int(s[i])
places[key].append(i)
for e in t:
key = int(e)
if not places[key]:
return False
i = places[key][-1]
for j in range(key):
if places[j] and places[j][-1] < i:
return False
places[key].pop()
return True
s = "95643"
t = "45963"
print(solve(s, t))
입력
"95643", "45963"
출력
True
복잡도 분석
시간 복잡도는 문자열의 길이를 n이라 할 때 O(n × 10), 즉 사실상 O(n)입니다. 각 문자에 대해 최대 10개의 자릿수(0~9)만 추가로 검사하기 때문입니다. 공간 복잡도 역시 모든 인덱스를 저장하므로 O(n)입니다.