github.com/onlybooks/algorithm-interview
1. 문제: 리트코드 344.Reverse String
문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라
2. 내 코드
def reverseString(self, s):
for i in range(len(s)):
s.insert(i, s.pop())
3. 투 포인터를 이용한 풀이
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
4. 파이썬다운 풀이
def reverseString(self, s: List[str]) -> None:
s.reverse()
5. 배운 점
1) 리스트를 뒤집을 때는 X.reverse() 사용 가능
2) in-place 알고리즘: 공간복잡도가 O(1)로 추가적인 저장공간을 필요로 하지 않는 알고리즘
ex)버블 정렬, 선택정렬은 in-place 알고리즘이지만 병합정렬, 퀵정렬 등은 in-place 알고리즘이 아니다.
'Computer Science > 알고리즘' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰] 6. 두 수의 합 (0) | 2022.02.02 |
---|---|
[파이썬 알고리즘 인터뷰] 5. 가장 긴 팰린드롬 부분 문자열 (0) | 2022.02.02 |
[파이썬 알고리즘 인터뷰] 4. 그룹 애너그램 (0) | 2022.02.02 |
[파이썬 알고리즘 인터뷰] 3. 가장 흔한 단어 (0) | 2022.01.31 |
[파이썬 알고리즘 인터뷰] 1. 로그 파일 재정렬 (0) | 2022.01.31 |