⭐️ LeetCode 알고리즘 풀이 (with Python)

# Reverse Words in a String

[Quetion]

LeetCode 151. Reverse Words in a String

📌 접근법

[문제 이해]

• 문자열을 단어 단위로 거꾸로 뒤집기
• ex) " hello world " ---> "world hello"
• 단어는 공백으로 분리, 문자열들의 맨 앞, 맨 뒤의 공백은 제거

단어가 공백을 기준으로 분리되어 있으므로 split()함수를 활용하여 공백 기준으로 분리하고, 스택의 원리를 활용하여 문자열을 뒤집는 접근법으로 생각했다.

💻 구현

class Solution:
    def reverseWords(self, s: str) -> str:
        s=s.split(' ')
        r=''
        while s:
            if s[-1] != '':
                r=r+s.pop()+' '
            else:
                s.pop()
        # 양쪽 공백 제거
        r=r.strip()
        return r

Runtime: 28ms | Memory: 16.2MB
LeetCode 코드 중 Runtime 98%, Memory 99% 해당하는 결과

📌 로직 핵심

• split() 함수로 공백 기준 분리
• 분리한 문자열이 담긴 리스트를 POP 하여 결과 문자열에 공백과 함께 더해가기
• 빈 값 (공백)일 경우 pass
• strip()함수로 제거되지 않은 문자열 양 끝단의 공백 제거

📝 Reverse Words in a String 회고

• 시간복잡도는 O(N)이지만 공간복잡도는 r에 더해가는게 전부이기 때문에 O(1)을 가진다.

• split()으로 분리된 문자열을 다른 리스트에 추가하는 방법으로도 쉽게 해결이 가능한 문제지만 그렇게 할 경우, 공간복잡도는 O(N)이 되므로 현재 방법을 선택했다.

• while문을 탈출하게 되면 ' abc def ' 에서 'def abc '가 되어 문자열 끝 부분에는 공백이 남게된다. 이를 해결하기 위해 양 끝단의 공백을 제거해주는 strip() 함수를 사용하므로써 간편하게 해결했다.