1963. Minimum Number of Swaps to Make the String Balanced

Problem : https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:01:09

 

---

 

문제 설명

 

 

0-인덱스의 짝수 길이 n의 문자열을 입력으로 받는다. 이 문자열은 정확히 n / 2 개의 여는 대괄호 '['와 닫는 대괄호 ']'로 구성되어 있다.

 

문자열은 다음 조건을 만족할 때 균형잡혔다고 말할 수 있다.

 

* 문자열이 비었거나,

* A, B가 균형잡힌 문자열일때 AB의 형태이거나

* C가 균형잡힌 문자열일때 [C]의 형태일 때.

 

임의의 두 개의 원소를 어떤 개수로든 교환할 수 있다고 할 때, 문자열 s를 균형잡히게 만들 수 있는 최소 경우의 수를 반환하라.

 

---

 

풀이

 

보자마자 딱 스택이라고 감이 온 문제. 문자열을 하나씩 탐색하여 균형잡힌 쌍을 전부 제거한다. (제거하는 방법은 스택을 이용하면 쉽다. 스택에 차례로 문자열을 담으며, 균형잡힌 쌍을 비교하며 제거하면 된다)

 

그렇다면 모든 문자열을 순회했을 때, 스택에 남은 문자들은 불균형잡힌 쌍이 남게 된다. 즉 정확히 이 시점에서의 스택의 길이의 반만큼 교환을 수행하면 최소 교환으로 s를 균형잡히게 만들 수 있는 셈이다.

 

풀이 코드

class Solution:
    def minSwaps(self, s: str) -> int:
        stack = []
        for _s in s :
            if stack and _s == ']' :
                stack.pop()
            else :
                stack.append(_s)
        return len(stack) // 2

풀이 완료