두 개의 숫자 문자열 s와 t가 있다고 가정하고 다음 작업을 여러 번 사용하여 문자열 s에서 t로 변환하려고 합니다. 1. s에서 비어 있지 않은 부분 문자열을 선택하고 문자가 오름차순으로 정렬되도록 제자리에서 정렬합니다. 문자열 s를 문자열 t로 변환할 수 있는지 여부를 확인해야 합니다.
따라서 입력이 s ="95643" t ="45963"과 같으면 "95643" -> "95463" -> "45963"을 사용하여 s를 t로 변환할 수 있으므로 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
장소 :=기본값 유형이 목록인 지도
-
s에서 0까지의 범위 크기에 있는 i에 대해
-
키 :=s[i] 정수로
-
장소[key]의 끝에 i 삽입
-
-
t의 각 e에 대해 수행
-
키 :=e를 정수로
-
장소[키]가 비어 있으면
-
거짓을 반환
-
-
i :=장소[key]의 마지막 요소
-
범위 0에서 키 - 1에 있는 j에 대해 수행
-
Places[j]가 비어 있지 않고 Places[j]
-
거짓을 반환
-
-
-
장소[key]에서 마지막 요소 삭제
-
-
-
참을 반환
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
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