[2024] day 123. Leetcode 2000. Reverse Prefix of Word

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 1일 (수)
Leetcode daily problem

2000. Reverse Prefix of Word

https://leetcode.com/problems/reverse-prefix-of-word/?envType=daily-question&envId=2024-05-01

Problem

문자열 word와 ch가 각각 주어 질때, 문자열 word에서 ch가 처음 등장하는 인덱스까지의 단어를 반대로 바꾸는 문자열을 반환한다.
만약 word에 ch에 해당하는 문자열이 없다면 그대로 word를 반환한다.

예를 들어서 word = 'abcdefd' 이고 ch='d인 경우
'd'가 처음 등장하는 인덱스는 word의 3이므로, 3까지의 단어를 뒤집어서 'dcba' 로 바꾼 후에 나머지 단어를 붙여 'dcbaefd'로 반환한다.

Solution

문자열 슬라이싱, 뒤집기 (string)

find 메소드를 사용해서 주어진 word에서의 인덱스를 찾는데,
인덱스가 없다면 그냥 word를 그대로 반환하고
찾았다면 해당 인덱스까지의 word를 슬라이싱하고, 그 슬라이싱한 단어를 거꾸로 변환한다음 나머지 단어를 붙여서 반환한다.

Code

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        if word.find(ch) == -1:
            return word
        
        idx = word.find(ch)
        prefix, postfix = word[:idx+1], word[idx+1:]
        
        return prefix[::-1]+postfix
            

Complexicity

시간 복잡도

문자열 word에서 특정 문자 ch를 찾고 뒤집는 과정에서 문자열 word의 길이인 O(n)까지 소요될 수 있으므로, 시간 복잡도는 O(n)이다.

공간 복잡도

주어진 문자열의 접두사(prefix)와 접미사(postfix)를 저장하기 위해 추가적인 공간을 사용하는데, 이 부분 문자열들은 입력 문자열과 같은 길이를 가지므로 공간 복잡도는 O(n)이다.

-> 공간복잡도를 O(1)로 소요시키기 위해서

먼저 idx를 구하고

word[:idx+1][::-1] + word[idx+1:] 하는 방법으로 한다면 O(1)로 풀 수 있다.

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        idx = word.find(ch)

        if idx == -1:
            return word
        
        return word[:idx+1][::-1] + word[idx+1:]

그 외의 솔루션으로 stack. two pointer를 사용해서 푸는 방법이 있다.

Stack으로 한번 풀어보자면 문자열 word에 있는 문자 하나 하나 씩 순환하면서 ch와 같은지 체크하고, 같지 않으면 스택에 넣고 같은 문자가 등장 경우 스택에 쌓인 문자들을 pop 하면서 문자열을 생성하고 나머지 뒤 문자열을 붙이는 형식이다.

해당 코드도 시간 복잡도 O(n), 공간 복잡도 O(n) 이다.

class Solution:
    def reversePrefix(self, word: str, ch: str) -> str:
        stack = []
        result = ''
        
        for i in range(len(word)):
            if word[i] == ch:
                result += word[i]
                while stack:
                    result += stack.pop()
                
                return result + word[i+1:]
                
            else:
                stack.append(word[i])
        
        return word