[Leetcode/Python] 1544. Make The String Great

문제 링크

Make The String Great - LeetCode

 

문제 설명

소문자와 대문자로 구성된 문자열 s가 주어집니다.
좋은 문자열은 다음과 같은 두 개의 인접한 문자 s[i] 및 s[i + 1]이 없는 문자열입니다.

- 0 <= i <= s.length - 2
- s[i]는 소문자이고 s[i + 1]은 동일한 문자이지만 대문자이거나 그 반대입니다.

문자열을 좋게 만들려면 문자열을 나쁘게 만드는 두 개의 인접한 문자를 선택하고 제거할 수 있습니다. 문자열이 좋아질 때까지 이 작업을 계속할 수 있습니다. 문자열을 잘 만든 후 반환합니다. 답은 주어진 제약 조건에서 고유함을 보장합니다.

빈 문자열도 좋습니다.

간단히 말해서 같은 문자가 연속이며, 소문자와 대문자가 같이 나오면 안 되는 뜻이다. leet은 되지만 leEt, lEet는 안되고, 이럴 경우 lt로 반환해야 한다.

 

입출력 예시

입력(s)	출력
"leEeetcode"	"leetcode"
"abBAcC"	""
"s"	"s"

 

제한 사항

• 1 <= s.length <= 100
• s는 오직 영어 소문자와 대문자로만 이루어져 있다.

 

문제 풀이

 처음에 간단히 하면 맞는 짝이 없을때까지 반복문을 돌리면 된다. 하지만 이 경우 O(n^2)의 시간 복잡도가 나오므로 효율이 그리 좋지 않다.

 

 따라서 이 문제는 투 포인터의 개념을 응용해서 풀어야 한다. 투 포인터는 두 곳을 표시해서 찾는 방법이지만, 이 문제의 경우 하나의 포인터만 필요하다. 나머지 한 포인터는 기존 포인터에서 -1을 해서 찾는 방식으로 하였다. 이 경우 시간 복잡도는 O(n)이며 공간 복잡도는 입력값 s 이외에 사용을 안 하므로 O(1)이 된다.

 

소스코드

class Solution:
    def makeGood(self, s: str) -> str:
        point = 1
        while point < len(s):
            if self.__isLowerUpper(s[point-1], s[point]):
                s = s[:point-1] + s[point+1:]
                if point > 1:
                    point-=1
            else:
                point+=1
        return s
    def __isLowerUpper(self, a: str, b: str) -> bool:
        if a.isupper() and b.islower() and a.lower() == b:
            return True
        elif b.isupper() and a.islower() and b.lower() == a:
            return True
        return False