[LeetCode] 1544. Make The String Great (Python)

LeetCode 1544. Make The String Great
🗓️ Daily LeetCoding Challenge November, Day 8
Stack

https://leetcode.com/problems/make-the-string-great/

Make The String Great - LeetCode

1. 문제 설명

문자열 s가 주어지고, 두 문자가 Good(?)인 경우 리턴하는 문제이다.

Good을 만족하는 조건은 다음과 같다.

s[i]가 소문자이고 s[i+1]가 같은 문자의 대문자이거나, 그 반대의 경우가 없어야 하므로 이를 제거한다.

 

아래와 같이 s가 주어진다고 가정하자.

s = "leEeetecode"

s[1]과 s[2]에서 e와 E가 인접하므로 두 문자를 제거한다.

혹은 s[2]와 s[3]에서 E와 e가 인접하므로 두 문자를 제거해도 결과는 같다.

따라서 "leetcode"를 리턴하면 된다.

---

2. 문제 접근

1. Naive approach

문제를 읽고 바로 드는 생각은 그냥 삭제하는 두 문자가 나오기 전까지 계속 loop를 돌리면 된다고 생각했다.

그러나 "ABCDEFGgfedcba"처럼 주어지면 loop의 반복 횟수가 상당하므로 엄청난 런타임을 가져올 것이다.

일단 이렇게 구현해서 제출해 봤는데, 역시나 상당히 비효율적인 런타임을 보여주었다.

 

2. Stack

스택은 Last in First out 자료형으로, 이와 같은 문제에서 엄청난 효율을 보여준다. (loop 한 번에 끝낼 수 있다.)

따라서 마지막에 넣은 문자열과 현재 넣을 문자열을 아스키코드로 비교하여 32를 기준으로 둘 중 하나를 수행하면 된다.

(차이가 32인 이유는 'A'가 65이고, 'a'가 97이기 때문이다. 나머지 알파벳의 차이도 32일 것이다.)

 

1. 두 문자의 아스키코드 차가 32인 경우 : 스택에서 가장 마지막에 들어온 문자를 pop한다.

2. 두 문자의 아스키코드 차가 32가 아닌 경우 : 스택에 현재 문자를 append한다.

 

스택으로 두 케이스를 처리하면 아스키코드 값의 차가 32인 문자는 둘 다 스택에 포함되지 않을 것이고,

이는 Good string을 보장한다. (empty string도 good string이다.)

---

3. 구현 코드

class Solution:
    def makeGood(self, s: str) -> str:
        stack = []
        for ch in s:
            if stack and abs(ord(ch) - ord(stack[-1])) == 32:  # 같은 알파벳, 대소문자인 경우
                stack.pop()
            else:  # 그 외의 경우 (스택에 넣어준다.)
                stack.append(ch)
                
        return ''.join(stack)

Naive하게 작성한 코드의 런타임은 올리지 않았지만 80ms이고, 스택으로 구현한 런타임은 49ms이다.

대략 30ms정도 빠르니 loop를 여러 번 도는 것이 비효율적임을 느낄 수 있다.

 

근데 제목에선 Great string 만든다면서.. 문제 설명에는 Good string이라고 언급한 이유가 있을까?