문자열 input_str이 주어졌다고 가정해 보겠습니다. 우리가 해야 할 일은 이 문자열에서 만들 수 있는 모든 부분 문자열을 구한 뒤, 이를 사전 순(lexicographical order)으로 하나씩 이어 붙여 새로운 문자열을 만드는 것입니다. 그리고 정수 값 k가 함께 주어지며, 최종적으로 연결된 문자열에서 인덱스 k에 해당하는 문자를 반환해야 합니다.
예를 들어 입력이 input_str = 'pqrs', k = 6이라면 출력 결과는 p가 됩니다.
주어진 문자열의 부분 문자열을 사전 순으로 나열하면 다음과 같습니다.
p, pq, pqr, pqrs, q, qr, qrs, r, rs, s
이 문자열들을 모두 이어 붙이면 ppqpqrpqrsqqrqrsrrss가 되고, 6번째 위치의 문자는 'p'입니다. (인덱스는 0부터 시작합니다.)
문제 해결 접근 방법
이 문제를 효율적으로 해결하기 위해 스택 기반 탐색 방식을 사용하며, 단계는 다음과 같습니다.
stk_list:= 빈 문자열과input_str의 모든 문자 위치(인덱스) 목록을 담은 튜플을 포함하는 새로운 리스트를 생성합니다.stk_list가 비어 있지 않은 동안 아래 과정을 반복합니다.pre:=stk_list에서 마지막 요소를 꺼냅니다(pop).temp:= 함께 저장된 위치 목록을 꺼냅니다.- 만약
k < len(pre)라면, 원하는 답은 이미 현재 접두사 안에 있으므로pre[k]를 반환합니다. - 그렇지 않으면
k -= len(pre)로 남은 인덱스를 갱신합니다. input_sorted:= 가능한 위치에 있는 문자들과 그다음 위치를 묶은 튜플 리스트를 만들고, 내림차순으로 정렬합니다. (스택의 LIFO 특성 때문에 내림차순으로 넣으면 꺼낼 때 사전 순으로 처리됩니다.)- 같은 문자가 연속으로 나오는 구간을 묶어
(pre + val, 다음 위치 목록)형태의 튜플을stk_list에 추가합니다.
- 모든 과정이 끝나면
None을 반환합니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(input_str, k):
stk_list = [("", list(range(len(input_str))))]
while stk_list:
pre, temp = stk_list.pop()
if k < len(pre):
return pre[k]
k -= len(pre)
input_sorted = sorted([(input_str[i], i + 1) for i in temp if i < len(input_str)], reverse=True)
i = 0
while i < len(input_sorted):
val = input_sorted[i][0]
temp1 = [input_sorted[i][1]]
j = i + 1
while j < len(input_sorted) and input_sorted[j][0] == val:
temp1.append(input_sorted[j][1])
j += 1
stk_list.append((pre + val, temp1))
i = j
return None
print(solve('pqrs', 6))입력
'pqrs', 6
출력
p
핵심 포인트 정리
이 알고리즘의 장점은 모든 부분 문자열을 실제로 생성해 이어 붙이지 않고도 k번째 문자를 찾을 수 있다는 점입니다. 전체 연결 문자열의 길이는 입력 길이 n에 대해 O(n²)에 비례해 매우 커질 수 있지만, 위 방식은 필요한 접두사만 스택에 쌓으며 탐색하기 때문에 메모리와 시간을 크게 절약할 수 있습니다. 특히 중복되는 문자 구간을 한 번에 묶어 처리하는 부분이 성능 최적화의 핵심입니다.