TIL 240621 - 알고리즘 코드카타 - 괄호 회전하기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

괄호들이 문자열로 주어지고, 문자열을 회전시켰을 때 올바른 괄호가 되는 경우의 수를 출력하는 문제이다.

 

2. 첫번째 시도

먼저 for문으로 문자열을 회전시키고, 내부의 for문으로 문자열의 괄호들을 검사한다.

이때, 괄호가 열리면 괄호에 해당하는 변수에 1을 더하고, 괄호가 닫히면 1을 빼는 식이다. 이때, 괄호가 열리기도 전에 닫히는 것은 불가능하므로, 순회 도중 변수가 0보다 작으면 카운트에서 제외하였다. 또한, 괄호는 짝이 맞아야 하므로 순회가 끝나고 해당 변수들이 모두 0이 되어야 카운트를 할 수 있도록 하였다.

function solution(s) {
  let [a1, a2, b1, b2, c1, c2] = ["[", "]", "{", "}", "(", ")"];
  let cnt = 0;
  for (let i = 0; i < s.length; i++) {
    let [aa, bb, cc] = [0, 0, 0];
    let isClosed = true;
    for (let j = i; j < i + s.length; j++) {
      let k = j % s.length;
      if (s[k] == a1) aa += 1;
      else if (s[k] == b1) bb += 1;
      else if (s[k] == c1) cc += 1;
      else if (s[k] == a2) aa -= 1;
      else if (s[k] == b2) bb -= 1;
      else if (s[k] == c2) cc -= 1;

      if (aa < 0 || bb < 0 || cc < 0) {
        isClosed = false;
        break;
      }
    }
    if ((isClosed = false || aa != 0 || bb != 0 || cc != 0)) continue;
    cnt+=1;
  }
  return cnt;
}

 

이때 문제점은, 괄호의 순서만 잘못되고 짝이 맞을 경우에도 카운트에 포함한다는 것이었다. '{(})' 같은 경우, 제대로 된 괄호가 아님에도 불구하고 카운트에 포함되었다.

 

3. 두번째 시도

새 배열을 만들어, 문자열을 순회하며 여는 괄호가 나타날 경우 배열에 차례대로 넣는다. 만약 닫는 괄호가 나타날 경우 배열의 끝 요소가 같은 종류의 여는 괄호일 경우 pop 하고, 다른 종류의 괄호일 경우 순회를 중단하고 카운트에서 제외한다.

function solution(s) {
  let [a1, a2, b1, b2, c1, c2] = ["[", "]", "{", "}", "(", ")"];
  let cnt = 0;
  for (let i = 0; i < s.length; i++) {
    let arr = [];
    let newS = s.slice(i) + s.slice(0,i);
    let isClosed = true;
    console.log("---------------------------")
    for (let k = 0; k < newS.length; k++) {

      if (newS[k] == a1) arr.push(a1);
      else if (newS[k] == b1) arr.push(b1);
      else if (newS[k] == c1) arr.push(c1);
      else if (newS[k] == a2 && arr[arr.length-1] == a1) {
        arr.pop();
      } else if (newS[k] == b2 && arr[arr.length-1] == b1) {
        arr.pop();
      } else if (newS[k] == c2 && arr[arr.length-1] == c1) {
        arr.pop();
      } else {
        isClosed = false;
        break;
      }
    }
    if (isClosed) cnt += 1;
  }
  return cnt;
}

 

이때 문제점은, 괄호가 여는 괄호밖에 없을 경우에도 순회가 완료되어 카운트에 포함된다는 것이었다. '({[' 같은 경우 닫는 괄호가 없어 순회가 중단되지 않고 카운트에 포함되었다.

 

3. 최종 코드

두번째 코드에서, 여는 괄호를 넣는 배열이 최종적으로 빈 배열일 때에만 카운트에 포함하도록 하였다.

let s = "[](){}";

function solution(s) {
  let [a1, a2, b1, b2, c1, c2] = ["[", "]", "{", "}", "(", ")"];
  let cnt = 0;
  for (let i = 0; i < s.length; i++) {
    let arr = [];
    let newS = s.slice(i) + s.slice(0, i);
    let isClosed = true;
    for (let k = 0; k < newS.length; k++) {
      if (newS[k] == a1) arr.push(a1);
      else if (newS[k] == b1) arr.push(b1);
      else if (newS[k] == c1) arr.push(c1);
      else if (newS[k] == a2 && arr[arr.length - 1] == a1) {
        arr.pop();
      } else if (newS[k] == b2 && arr[arr.length - 1] == b1) {
        arr.pop();
      } else if (newS[k] == c2 && arr[arr.length - 1] == c1) {
        arr.pop();
      } else {
        isClosed = false;
        break;
      }
    }
    if (isClosed && arr.length==0) {
      cnt += 1;
      console.log(cnt);
    }
  }
  return cnt;
}

console.log(solution(s));

 

4. 새로 알게된 것

1) 배열이 빈 배열인지 확인하려면 arr==[]를 쓰면 제대로 작동이 안된다. arr.length==0을 쓰자.

2) 무언가 짝을 맞추거나 순서가 중요한 문제는 새 배열에 하나씩 push/pop 하는 방법을 생각해보자. 돌이켜보면 이전에도 push/pop을 이용하면 편하게 풀 수 있는 문제들이 많았다.