백준4889 - 안정적인 문자열 (스택) node.js

https://www.acmicpc.net/problem/4889

 

문제 해결 방식

일반적인 스택 문제를 응용하여 해결했다.

먼저 스택에 '{}'이 삽입될 경우, 이는 문자열이 안정된 경우이므로 우선 삭제하여 스택에 쌓이는 원소를 최소화하였다.

이후 스택에 남은 원소들을 변화시키되, 괄호를 변환시키는 횟수를 최소화하여야 하는데, 이때는 스택에 쌓인 원소를 두개씩 짝을지어 삭제시키고 때마다 변환시키는 횟수에 추가했다.

예를 들어, '}{'로 두 원소가 다른 경우는 올바른 문자열로 만들기 위해서 두 원소를 모두 변화시켜야 하므로 2회를 변환 횟수에 추가하고

'}}' 또는 '{{'와 같이 두 원소가 모두 같은 경우는 둘 중 하나만 바꾸어도 올바른 문자열이 되기 때문에 1회 연산을 변환 횟수에 추가했다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  data.pop();

  const result = data.map((el, idx) => {
    return `${idx + 1}. ${act(el)}`;
  });

  console.log(result.join("\n"));
}

function act(str) {
  const arr = str.split("");
  const stack = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === "{") stack.push("{");
    else if (arr[i] === "}" && stack.at(-1) === "{") stack.pop();
    else stack.push("}");
  }

  if (!stack.length) return 0;

  let cnt = 0;

  while (stack.length) {
    const a = stack.pop(),
      b = stack.pop();

    cnt += a !== b ? 2 : 1;
  }

  return cnt;
}

solution(input);