•
문제 링크 : leetcode.com
•
문제 설명 : s 문자열과, indices indexs가 서로 매핑되어 제공된다. 이때 indices를 오름차순 정렬했을 때 새로운 문자열을 반환하면된다.
•
풀이 방법
◦
zip 함수를 사용하여 s와 indices를 연결된 iterator를 생성한 뒤, sorted의 정렬 조건을 lambda로 설정하여 정렬해준다.
◦
정렬된 iterator의 첫 번째 원소는 s를 구성하던 문자들이기 때문에, 이 문자들만 그대로 사용하여 반환에 필요한 데이터를 생성하였다.
◦
join 없이, 바로 별도의 변수에 문자열을 연결하면 시간복잡도가 O(N) 만큼 감소할 것 같다.
▪
변경 후 제출하였을때는 큰 차이가 없어, 그냥 아래코드로 작성하였지만 이후 대량의 데이터를 다룰 때는 참고하면 될 것 같다.
•
시간복잡도 :
•
성공 코드
# O(N)[zip함수] + O(NlogN)[sorted(iterator, key)] + O(N)[컴프리헨션 내 for] + O(N)[join] -> O(NlogN)
class Solution:
def restoreString(self, s: str, indices: List[int]) -> str:
# zip을 사용하여, s와 indices의 각 요소가 결합된 새로운 객체를 만든다.
# 이때, 가장 짧은 시퀀스의 길이를 사용하며, O(N)이다.
zip_object = zip(s, indices)
# key를 사용하는 sorted 함수의 시간 복잡도
# 각 요소마다 key 함수 호출 -> O(N)
# sorted 함수는 Timsort 알고리즘 사용, 이는 병합정렬과 삽입정렬을 결합한 알고리즘
# Timsort 알고리즘 : 정렬이 필요한 배열을 잘게 잘라서 삽입 정렬로 정렬 후, 병합정렬로 최종 병합 / 이미 어느정도 정렬된 데이터임을 가정하고 사용
# Timsort 알고리즘은 최종적으로는 병합정렬을 사용하기 때문에, O(NlogN)의 시간복잡도가 소요된다.
# 따라서, sorted(zip_object, key=lambda x: x[1])는 O(N + NlogN) -> O(NlogN) 시간복잡도이다.
# 추가적으로, 컴프리헨션내 for문을 사용한 순회 -> O(N)
# join() 함수에서의 데이터 순회 -> O(N)
return "".join([ch for ch, i in sorted(zip_object, key=lambda x: x[1])])
Python
복사