LeetCode (C/C++, Java) 1963. Minimum Number of Swaps to Make the String Balanced

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

---

풀이

힌트를 보고 투 포인터와 스택을 사용하는 것임을 알았다.

처음(C/C++ 코드)에는 인덱스를 늘려가며 닫힌 괄호를 만났을 때 열린 괄호가 있는지를 확인하고, 없다면 뒤의 열린 괄호를 찾아 swap 하였다.

 

속도가 느려서 답지(Java 코드)를 찾아보니, 닫힌 괄호를 만났을 때 열린 괄호의 개수만을 세서 확인해서 이 방식으로도 풀어보았다. 

 

열린 괄호와 닫힌 괄호의 갯수는 동일하므로, 남아있는 열린 괄호의 개수(openCnt) 값이 짝을 다 맞추고 남아있는 불균형의 개수이므로 해당 값이 최소 교환 횟수를 보장한다.

---

C/C++ 코드

class Solution {
public:
    int minSwaps(string s) {
        int start = 0, end = s.size() - 1;
        int openCnt = 0, cnt = 0;

        while (start <= end) {
            if (s[start] == ']') {
                
                // 닫힌 괄호일 때 열린 괄호가 없다면
                if (openCnt <= 0) {
                
		            // 열린 괄호를 찾아 바꿔줌
                    while (s[end] == ']') end--;
                    s[end] = ']';
                    openCnt++;

                    // swap 횟수 저장
                    cnt++;
                }
                
                // 열린 괄호가 있다면 열린 괄호의 개수 감소
                else openCnt--;
            }
						
	        // 열린 괄호를 만났다면 열린 괄호 개수 증가
            else openCnt++;
            
            start++;
        }
        return cnt;
    }
};

 

Java 코드

class Solution {
    public int minSwaps(String s) {
        int openCnt = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (c == ']') {
                // 열린 괄호가 없을 때 -> 불균형 추가
                if (openCnt == 0)
                    openCnt++;
                else
                    openCnt--;
            }
            // 열린 괄호일 경우 열린 괄호 개수 추가
            else openCnt++;
        }
        // 불균형한 부분을 swap으로 바꾸므로 / 2 수행
        return (openCnt + 1) / 2;
    }
}