[2024] day 97. Leetcode 1544. Make The String Great

gunny·2024년 4월 7일

1544. Make The String Great 1544. Make The String Great python leetcode 1544. Make The String Great leetcode 1544. Make The String Great python

코딩테스트

목록 보기

410/530

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

2024년 4월 5일 (금)
Leetcode daily problem

1544. Make The String Great

https://leetcode.com/problems/make-the-string-great/?envType=daily-question&envId=2024-04-05

Problem

영어 소문자와 대문자로 구성된 문자열 s가 있을 때,
좋은 문자열은 두 개의 인접한 문자 s[i] 및 s[i + 1]이 없는 문자열이다.

"0 <= i <= s.길이 - 2"

s[i]는 소문자이고 s[i + 1]은 동일한 문자이지만 대문자이거나 그 반대입니다. 문자열을 양호하게 만들려면 문자열을 양호하게 만드는 두 개의 인접한 문자를 선택하고 제거할 수 있다. 문자열이 좋아질 때까지 이 작업을 계속 반복할 수 있다.
문자열을 좋게 만든 후 반환한다. 응답은 주어진 제약 조건 하에서 고유한 것으로 보장됩니다. 빈 문자열이 된다면 빈 문자열을 반환한다.

Solution

stack

문자열을 순회하면서 스택에 문자를 하나씩 넣어가면서 다음 문자를 넣을 때 스택의 가장 위에 있는 문자와 쌍을 이루는지 확인한다.
쌍을 이루는 문자가 있다면 해당 문자들을 스택에서 제거하고, 쌍을 이루지 않는다면 스택에 추가한다.
마지막 스택에 있는 문자들을 조합하여 반환하면된다.

해당 문자열이 쌍을 이루는 대소문자인지 확인하는 방법은
아스키코드로 변경하여 둘의 차이가 32가 나오는지 확인하거나,
python의 swapcase()를 사용하는 것이다.

Code

class Solution:
    def makeGood(self, s: str) -> str:
        stack = []        
        for char in s:
            if stack and stack[-1] == char.swapcase():
                stack.pop()
            else:
                stack.append(char)
        return ''.join(stack)

class Solution:
    def makeGood(self, s: str) -> str:
        stack = []        
        for char in s:
            if stack and stack[-1] == char.swapcase():
                stack.pop()
            else:
                stack.append(char)
        return ''.join(stack)

Complexicity

시간 복잡도

문자열의 길이를 n이라고 했을 때, for 루프를 통해 문자열의 모든 문자를 한 번씩 순회할 때, O(n)의 시간이 소요된다.
스택에서 pop 및 append 작업은 상수 시간이 걸린다. 따라서 스택 연산에 소요되는 시간은 O(1)이다.
따라서 전체적으로는 O(n)의 시간 복잡도를 가진다.

공간 복잡도

입력 문자열과 같은 길이의 스택을 사용하므로, 추가적인 공간은 문자열 길이에 비례한다. 따라서 공간 복잡도는 O(n)입니다.

swapcase 사용의 경우