문자열 s와 인덱스 리스트 ind가 주어졌을 때, 두 값의 길이는 서로 같다고 가정해 봅시다. 문자열 s는 원래 위치 i에 있던 문자가 최종 결과 문자열의 indices[i] 위치로 이동하는 방식으로 재배치(shuffle)됩니다. 우리의 목표는 최종적으로 만들어지는 문자열을 구하는 것입니다.
예를 들어 입력이 다음과 같다면,
- s = "ktoalak"
- ind = [0,5,1,6,2,4,3]
출력은 "kolkata"가 됩니다. 각 문자가 지정된 인덱스 위치로 이동하면서 원래 의미 있는 단어로 복원되는 것입니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- fin_str이라는 리스트를 생성합니다. 크기는 문자열 s와 동일하게 하고, 모든 요소를 0으로 초기화합니다.
- enumerate를 사용해 문자열 s의 각 인덱스 i와 문자 v를 순회하며 다음 작업을 수행합니다.
- fin_str[ind[i]] := v — 즉, 현재 문자 v를 목표 인덱스 위치에 배치합니다.
- 모든 배치가 끝나면 fin_str의 문자들을 하나로 연결(join)하여 반환합니다.
파이썬 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(s, ind):
fin_str = [0] * len(s)
for i, v in enumerate(s):
fin_str[ind[i]] = v
return "".join(fin_str)
s = "ktoalak"
ind = [0,5,1,6,2,4,3]
print(solve(s, ind))입력
"ktoalak", [0,5,1,6,2,4,3]
출력
kolkata
코드 설명 및 시간 복잡도
이 알고리즘의 핵심은 O(n) 시간 복잡도로 동작한다는 점입니다. 문자열의 길이만큼 한 번씩 순회하면서 각 문자를 정확한 위치에 바로 배치하기 때문입니다. 공간 복잡도 역시 결과를 저장할 리스트 크기인 O(n)입니다.
또한 파이썬에서는 zip 함수를 활용해 더 간결하게 표현할 수도 있습니다.
def solve(s, ind):
result = [''] * len(s)
for i, target in enumerate(ind):
result[target] = s[i]
return ''.join(result)두 방식 모두 동일한 결과를 반환하지만, 인덱스와 값을 함께 다루는 상황에서는 enumerate를 사용하는 첫 번째 방식이 가독성 면에서 유리합니다. 이러한 기법은 문자열 재배치 문제뿐 아니라 이미지 픽셀 순서 변경, 데이터 셔플링 등 다양한 분야에서 응용될 수 있습니다.