안정적인 문자열

문제

언어

  • JavaScript

순서도

  1. 간단한 스택 구현 또는 배열 사용
  2. 스택을 이용해서 주어진 문자열에서 안정적인 문자열 모두 제거
  3. 스택에 남아있는 불안정적인 문자열에 대해서 안정적인 문자열로 바꿔주고 횟수 세기

문제 풀이 step 1

  • 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어집니다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 합니다.
  • 안정적인 문자열의 정의란 다음과 같습니다.
    1. 빈 문자열은 안정적이다.
    2. S 가 안정적이라면, {S} 도 안정적인 문자열입니다.
    3. S 와 T 가 안정적이라면, ST (두 문자열의 연결)도 안정적입니다.
  • 문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2 가지입니다.

문제 풀이 step 2

  • 위의 안정적인 문자열의 정의를 참고해서 풀면 되겠습니다.
  • 우선, 주어진 문자열에 대해서 스택을 이용해서 안정적인 문자열을 모두 제거했습니다.
    • 주어진 문자열을 안정적으로 바꾸는데 필요한 연산을 최소로 줄이기 위해서
  • 그리고 만약 안정적인 문자열을 모두 제거해도, 문자열이 남아있다면 이들만 안정적인 문자열로 바꿔주면 되겠습니다.
    • 남아있는 문자열에 대해서 앞에서부터 차례로 안정적으로 바꿔주고, 바꾼 횟수를 세어주면 되겠습니다.
  • 위의 연산을 모두 마치고 바꾼 횟수를 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 어떻게 하면 연산의 횟수를 최소로 줄일 수 있을까에 대해서 생각을 하며, 안정적인 문자열을 모두 제거하고 불안정적인 문자열을 순서대로 바꿔주면 되지 않을까 라는 접근법으로 풀었습니다.
  • 그리디의 성향을 가지고 있는 문제인 것 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	let res = "";

	let index = 0;
	while (true) {
		const str = input[index++];
		if (str[0] === "-") break;

		let cnt = 0;
		const stack = [];
		// 안정적인 문자열 모두 제거
		for (let i = 0; i < str.length; i++) {
			const ch = str[i];

			if (stack.length) {
				const top = stack[stack.length - 1];

				if (top === "{" && ch === "}") stack.pop();
				else stack.push(ch);
			} else {
				stack.push(ch);
			}
		}

		// 불안정적인 문자열들 앞에서부터 순차적으로 안정적인 문자열로 바꿔주기
		if (stack.length) {
			for (let i = 0; i < stack.length; i += 2) {
				if (stack[i] === "}") cnt += 1;
				if (stack[i + 1] === "{") cnt += 1;
			}
		}

		res += `${index}. ${cnt}\n`;
	}

	return res;
};

console.log(solution(input));