Portfolio

문제

1963. Minimum Number of Swaps to Make the String Balanced

Medium

403

Add to List

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

It is the empty string, or

It can be written as AB, where both A and B are balanced strings, or

It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

Example 1:


Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".

Example 2:


Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".

Example 3:


Input: s = "[]"
Output: 0
Explanation: The string is already balanced.

Constraints:

n == s.length

2 <= n <= 106

n is even.

s[i] is either '[' or ']'.

The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

풀이

재영


const minSwaps = (s) => {
  let cnt = 0; // result
  let start = 0; // two-pointer first
  let end = s.length - 1; // two-pointer end
  let left = 0;
  let right = 0;

  while (start < end) {
    updateCount(s[start]);
    if (right > left) {
      while (left !== right) {
        updateCount(s[end]);
        end -= 1;
      }
      right -= 1;
      cnt += 1;
    }
    start += 1;
  }

  return cnt;

  function updateCount(value) {
    if (value === "[") left += 1;
    else right += 1;
  }
};

은찬


const minSwaps = (s) => {
    let count = 0;
    
    for(let i = 0; i < s.length; i++){
        if(s[i] === "["){
            count++;
        } else if(count > 0){
            count--;
        }
    }
    
    return Math.ceil(count / 2);
};

효성

시간초과..


var minSwaps = function(s) {
    let S = s.split('');
    let leftIdx = 0;
    let rightIdx = s.length -1;
    let answer = 0;
    
    while(leftIdx < rightIdx) {
        if(S[leftIdx] !== '[' && S[rightIdx] !== ']') {
            [S[leftIdx], S[rightIdx]] = [S[rightIdx], S[leftIdx]];
            answer++;
            leftIdx++;
            rightIdx--;
        }
        else if(S[leftIdx] !== '[' && S[rightIdx] === ']') {
            rightIdx--;
        }
        else if(S[leftIdx] === '[' && S[rightIdx] !== ']') {
            leftIdx++;
        }
        else {
            leftIdx++;
            rightIdx--;
        }
        if(isBalanced(S)) {
            return answer;
        }
    }
    return answer;
};

function isBalanced(str) {
    let condition = 0;
    for(let i=0; i<str.length; i++) {
        str[i] === '[' ? condition++ : condition--;
        if(condition < 0) {
            return false;
        }
    }
    return true;
}

참고풀이

🤔 왜 반올림하면 정답이지..?


var minSwaps = function(s) {
    var mismatch  = 0;
    var cnt = 0;
    for(var i=0; i<s.length; i++)
    {
        if(s[i] === ']')
        {
            cnt--;
        }
        else
        {
             cnt++;
        }
        if(cnt < 0)
        {
            mismatch = Math.min(mismatch, cnt);
        }
    }
    return  Math.ceil(-mismatch/ 2);
};

Minimum Number of Swaps To Make The String Balanced

문제

풀이

시간초과..

참고풀이