문자열 'input_str'이 주어졌다고 가정합니다. 이제 주어진 문자열에서 가능한 모든 하위 문자열을 결정한 다음 모든 하위 문자열을 어휘 순서대로 다른 문자열로 연결하라는 요청을 받습니다. 정수 값 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가 비어 있지 않은 동안 do
- pre :=stk_list에서 마지막 요소 삭제
- temp :=stk_list에서 마지막 요소 삭제
- k
- 반환 프리[k]
- k :=k - 사전 크기
- input_sorted :=input_str의 문자와 input_str에서의 위치를 포함하는 튜플을 포함하는 새 목록
- 튜플의 두 번째 값을 기준으로 input_sorted 목록을 내림차순으로 정렬
- i :=0
- 내가
- val :=input_sorted[i, 0]
- temp1 :=[input_sorted[i, 1]]
- j :=나는 + 1
- j
- temp1의 끝에 input_sorted[j, 1] 삽입
- j :=j + 1
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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