두 개의 문자열 s와 t가 있다고 가정합니다. 다음과 같은 방법으로 merge라는 문자열을 만들어야 합니다. s 또는 t가 비어 있지 않은 동안 다음 옵션 중 하나를 선택합니다. -
-
s가 비어 있지 않은 경우 s의 첫 번째 문자를 추가하여 s에서 병합 및 삭제합니다.
-
t가 비어 있지 않은 경우 t의 첫 번째 문자를 추가하여 t에서 병합하고 삭제합니다.
따라서 사전순으로 가장 큰 병합을 찾아야 합니다.
따라서 입력이 s ="zxyxx" t ="yzxxx"와 같으면 출력은 zyzxyxxxxx가 됩니다. 왜냐하면
-
s에서 선택:merge ="z", s ="xyxx", t ="yzxxx"
-
t에서 선택:병합 ="zy", s ="xyxx", t ="zxxx"
-
t에서 선택:merge ="zyz", s ="xyxx", t ="xxx"
-
s에서 선택:merge ="zyzx", s ="yxx", t ="xxx"
-
s에서 선택:merge ="zyzxy", s ="xx", t ="xxx"
그런 다음 병합이 끝날 때 s와 t에서 나머지 5개의 x를 추가합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ans :=빈 문자열
-
아이디x1 :=0, 아이디x2 :=0
-
동안 idx1
-
s[idx1]> t[idx2] 또는 (s[idx1]이 t[idx2]와 동일하고 s[인덱스 idx1에서 끝까지]>=t의 부분 문자열[인덱스 idx2에서 끝까지]과 같으면
-
ans :=ans 연결 s[idx1]
-
idx1 :=idx1 + 1
-
-
그렇지 않으면 s[idx1]
-
ans :=ans 연결 t[idx2]
-
idx2 :=idx2 + 1
-
-
-
return ans concatenate s[index idx1에서 end] concatenate t[index idx2에서 end]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(s, t):
ans = ""
idx1 = idx2 = 0
while(idx1<len(s) and idx2<len(t)):
if s[idx1]>t[idx2] or (s[idx1]==t[idx2] and s[idx1:]>=t[idx2:]):
ans+=s[idx1]
idx1+=1
elif s[idx1]<t[idx2] or (s[idx1]==t[idx2] and s[idx1:]<=t[idx2:]):
ans+=t[idx2]
idx2+=1
return ans+s[idx1:]+t[idx2:]
s = "zxyxx"
t = "yzxxx"
print(solve(s, t))
입력
[7,4,5,3,8], [[0,2,2],[4,2,4],[2,13,100]]
출력
zyzxyxxxxx