문제 개요
두 개의 문자열이 주어져 있고, 이 문자열들을 조합해 사전순(lexicographically)으로 가장 작은 문자열을 만들려고 합니다. 문자열을 구성하는 규칙은 다음과 같습니다. 매 단계마다 두 문자열의 현재 첫 글자를 비교하여, 사전순으로 더 작은 글자를 해당 문자열에서 추출해 결과 문자열에 붙입니다. 두 글자가 같아 동률인 경우에는 첫 번째 문자열에서 글자를 가져옵니다. 이 과정을 두 문자열이 모두 빌 때까지 반복하며, 최종적으로 완성된 최소 문자열을 반환해야 합니다.
예를 들어 입력이 input_1 = 'TUTORIALS', input_2 = 'POINT'라면 결과는 다음과 같습니다.
POINTTUTORIALS
두 문자열을 한 글자씩 비교해 가는 과정을 단계별로 살펴보면 다음과 같습니다.
TUTORIALS POINT
TUTORIALS OINT = P
TUTORIALS INT = PO
TUTORIALS NT = POI
TUTORIALS T = POIN
TUTORIALS = POINT
어느 시점에서 한 문자열이 먼저 소진되면, 남은 다른 문자열 전체가 그대로 결과 문자열 뒤에 붙습니다. 위 예시에서는 'POINT'가 모두 추출된 후 'TUTORIALS' 전체가 이어붙여져 최종 문자열 POINTTUTORIALS가 됩니다.
알고리즘 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- input_1 := input_1 + "z"
- input_2 := input_2 + "z"
- temp_1 := 0
- temp_2 := 0
- res_str := 빈 문자열
- temp_1 < input_1의 길이이고 temp_2 < input_2의 길이인 동안 반복:
- 만약 input_1[temp_1부터 끝까지] < input_2[temp_2부터 끝까지]라면:
- res_str := res_str + input_1[temp_1]
- temp_1 := temp_1 + 1
- 그렇지 않으면:
- res_str := res_str + input_2[temp_2]
- temp_2 := temp_2 + 1
- 만약 input_1[temp_1부터 끝까지] < input_2[temp_2부터 끝까지]라면:
- res_str := res_str[0부터 마지막에서 두 번째 원소까지]
- 만약 temp_1 < len(input_1)이라면:
- res_str := res_str + input_1[temp_1부터 마지막에서 두 번째 원소까지]
- 만약 temp_2 < len(input_2)라면:
- res_str := res_str + input_2[temp_2부터 마지막에서 두 번째 원소까지]
- return res_str
여기서 각 문자열 끝에 소문자 'z'를 붙이는 것은 센티널(sentinel) 기법입니다. 대문자 알파벳(A~Z)보다 ASCII 값이 큰 'z'를 표식으로 사용하면, 한 문자열이 모두 소진된 시점에도 비교 연산이 자연스럽게 처리되고, 마지막에 이 표식 문자를 잘라내어 정답을 얻을 수 있습니다.
예제
다음 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
def solve(input_1, input_2):
input_1 += "z"
input_2 += "z"
temp_1 = 0
temp_2 = 0
res_str = ""
while temp_1 < len(input_1) and temp_2 < len(input_2):
if input_1[temp_1:] < input_2[temp_2:]:
res_str += input_1[temp_1]
temp_1 += 1
else:
res_str += input_2[temp_2]
temp_2 += 1
res_str = res_str[:-1]
if temp_1 < len(input_1):
res_str += input_1[temp_1:-1]
if temp_2 < len(input_2):
res_str += input_2[temp_2:-1]
return res_str
print(solve('TUTORIALS', 'POINT'))입력
'TUTORIALS', 'POINT'
출력
POINTTUTORIALS