[코테연습] 1963. Minimum Number of Swaps to Make the String Balanced

- 스택 / 문자열 문제

 

https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/description/?envType=daily-question&envId=2024-10-08

 

- 문제분석

1. '[' 와 ']' 로 되어있는 문자열이 있다.

2. 이 문자열은 '[' 와 ']' 이 같은 숫자로 구성되어있다.

3. 괄호가 랜덤하게 배열되어있을 때, 괄호가 닫혀있는 구성 ( ex ) [[][]] , [[[]]] ) 인 경우를 만들기 위해 최소한의 스왑 갯수를 구해라.

 

- 문제풀이

1. 여는 괄호 ( ' [ ' ) 보다 닫는 괄호 ( ' ] ' ) 가 많을 때, 스왑한다고 가정하고 스왑 갯수를 1 늘린다.

2. 여는 괄호로 초기화하기 위해 open 을 1로 초기화한다.

 

> java

 

class Solution {
    /**
    
     */
    public int minSwaps(String s) {
        int count = 0;
        int open = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            
            char c = s.charAt(i);
            if ( c == '[' ) {
                open++;
            } else {
                open--;
            }
            if (open < 0) {
                count++;
                open = 1;
            }
        }

        return count;
    }

}

 

> python

 

class Solution:
    def minSwaps(self, s: str) -> int:
        count = 0
        open = 0
        n = len(s)
        for i in range(n) :
            if s[i] == '[' :
                open+=1
            else :
                open-=1
            if open < 0 :
                count+=1
                open=1
                

        return count