문자열 문제 풀이

• 알고리즘 5주차 주제는 문자열이었다.
• 역시나 기억에 남는 문제 위주로 푼 문제를 정리해본다.

---

 

백준 4889번

  문제가 어째 익숙한 느낌이 들었는데, 예전에 풀었던 4949번 균형잡힌 세상 문제와 비슷한 괄호 문제였다. 다만 약간의 차이가 존재하는데, 4949번은 괄호가 포함된 문자열을 탐색하고, 괄호가 올바른지(균형 잡혔는지)의 여부를 확인하는 문제였다면, 이 문제는 올바르지 않은(안정적이지 않은) 괄호 문자열을 최소 몇 번 수정해야 옳게 만들 수 있는지를 확인해야 한다.

  따라서 4949번처럼 괄호를 스택에 넣고 빼며, 첫째로 괄호로 이루어진 문자열이 안정적인지 확인한다. 만약 스택에 남은 요소가 없다면 이미 괄호 문자열은 안정적인 상태이므로 수정할 필요가 없음을 의미한다. 만약 스택에 남은 요소가 있다면, 해당 요소들을 살펴보며 안정적인 괄호가 될 수 있도록 수정한다. 이 때 그리디적인 풀이방법을 적용했다. 안정적인 괄호 문자열이란 곧 괄호({})의 짝이 맞는 괄호이기 때문에, 괄호를 2개씩 살펴보며 짝을 맞춰주는 식으로 변경하는 방법이 그것이다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

class Stack {
  constructor(size) {
    this.array = new Array(size + 1);
    this.top = -1;
  }
  push(el) {
    if (this.top === this.array.length - 1) return -1;
    this.array[++this.top] = el;
  }
  pop() {
    if (this.top === -1) return -1;
    return this.array[this.top--];
  }
  isEmpty() {
    return this.top === -1;
  }
  getTop() {
    return this.array[this.top];
  }
}

rl.on("line", (line) => {
  input.push(line);
}).on("close", function () {
  let answer = "";

  for (let i = 0; i < input.length - 1; i++) {
    const str = input[i];
    const stack = new Stack(str.length);

    for (let j = 0; j < str.length; j++) {
      if (str[j] === "{") stack.push(str[j]);
      if (str[j] === "}") {
        if (stack.getTop() === "{") stack.pop();
        else stack.push(str[j]);
      }
    }

    if (stack.isEmpty()) {
      answer += `${i + 1}. 0\n`;
    } else {
      let num = 0;
      const unstableStr = stack.array.slice(0, stack.top + 1);
      for (let j = 0; j < unstableStr.length; j = j + 2) {
        if (unstableStr[j] === unstableStr[j + 1]) {
          num++;
        } else {
          num += 2;
        }
      }
      answer += `${i + 1}. ${num}\n`;
    }
  }

  console.log(answer.trim());

  process.exit();
});

 

 

백준 9935번

  문자열 내에 폭발 문자열이 제거되는 폭발이 모두 일어난 후, 남은 문자열을 구하는 문제. 문자열은 폭발 문자열의 폭발 → 남은 문자열끼리합쳐짐 → 합쳐진 문자열에 폭발 문자열 존재 시 다시 폭발 → 모든 폭발이 끝남의 과정을 거친다.

  처음에는 맨 첫 폭발을 String.split()으로 처리하고, 남은 문자열들을 스택에 넣은 후, 스택에서 문자열을 꺼내어 붙이다 폭발 문자열이 만들어지면 다시 문자열을 쪼개는 방식으로 구현했었다. 다만 이 방식은 메모리 초과를 내는데, 찾아보니 String.split()이 원인인듯 싶었다. String.split()은 문자열의 길이에 따라 그 성능이 좌우되는데, 이 문제의 경우 입력의 길이가 백만까지이기 때문에 성능이 크게 떨어졌던 것.

  그래서 split을 배제하고, 최대한 스택을 활용하는 방향으로 코드를 수정하니 맞았다. 로직을 풀면 다음과 같다.

1. 문자열을 순회하며 문자 하나하나를 스택에 넣는다.
2. 문자를 스택에 넣을 때마다, 스택 배열을 폭탄 문자열의 길이만큼 잘라 폭탄 문자열이 만들어지는지 확인한다. 만약 폭탄 문자열이 만들어졌다면, 스택의 top을 폭탄 문자열의 길이만큼 이동시키는 것으로 스택에서 문자열을 잘라낸다.
3. 문자열의 순회가 끝나면, 스택에 남아있는 문자들을 합쳐 출력한다. 스택에 남은 문자열이 없다면 FRULA를 출력한다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

class Stack {
  constructor(size) {
    this.stack = new Array(size + 1);
    this.top = -1;
  }

  push(el) {
    if (this.top === this.stack.length - 1) return -1;
    else this.stack[++this.top] = el;
  }

  pop() {
    if (this.top === -1) return -1;
    else return this.stack[this.top--];
  }

  isEmpty() {
    return this.top === -1;
  }
}

rl.on("line", (line) => {
  input.push(line);
}).on("close", function () {
  const [str, bomb] = input;

  const stack = new Stack(str.length);

  for (let i = 0; i < str.length; i++) {
    stack.push(str[i]);

    const sliced = stack.stack
      .slice(stack.top - bomb.length + 1, stack.top + 1)
      .join("");

    if (sliced === bomb) {
      stack.top -= bomb.length;
    }
  }
  const answer = stack.stack.slice(0, stack.top + 1).join("");
  console.log(answer === "" ? "FRULA" : answer);

  process.exit();
});

 

 

백준 17609번

  팰린드롬(회문)문제. 주어진 문자열을 확인하여 그것이 회문인지, 한 문자를 삭제하면 회문이 되는 유사 회문인지, 그 어느것도 아닌 일반 문자열인지를 판단하여 출력하는 문제였다.

  전에도 팰린드롬 문제를 풀었던 적이 있었는데, 안일하게도 그때 활용한 풀이방법을 이번에도 이용해보겠다고 애쓰다가 시간만 낭비했다. 최종적으로는 투 포인터를 적극적으로 활용하여 문제를 풀었다.

1. 투 포인터를 사용해 문자열의 양 끝에서부터 문자들을 비교하기 시작한다.
2. 만약 처음으로 서로 다른 문자들이 나타났다면, 그 때부터 2가지의 케이스를 테스트한다.
   - 좌측에 있는 문자를 삭제했을때, 남은 문자열이 회문이 되는지 확인한다.
   - 우측에 있는 문자를 삭제했을때, 남은 문자열이 회문이 되는지 확인한다.
3. 위의 경우에서 하나라도 회문이 되는 경우가 있으면 그 문자열은 유사 회문이다. 그 어느 케이스도 회문이 되지 못한다면, 일반 문자열이다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

const checkPalindrome = (str) => {
  let left = 0,
    right = str.length - 1;

  while (left < right) {
    if (str[left] === str[right]) {
      left++;
      right--;
    } else {
      let isLeftPalindrome = false,
        isRightPalindrome = false;

      if (str[left] === str[right - 1]) {
        isLeftPalindrome = true;
        let a = left,
          b = right - 1;
        while (a < b) {
          if (str[++a] !== str[--b]) {
            isLeftPalindrome = false;
            break;
          }
        }
      }
      if (str[left + 1] === str[right]) {
        isRightPalindrome = true;
        let a = left + 1,
          b = right;
        while (a < b) {
          if (str[++a] !== str[--b]) {
            isRightPalindrome = false;
            break;
          }
        }
      }

      return isLeftPalindrome || isRightPalindrome ? 1 : 2;
    }
  }
  return 0;
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", function () {
  const n = parseInt(input.shift());
  const answer = [];

  for (let i = 0; i < n; i++) {
    answer.push(checkPalindrome(input[i]));
  }
  console.log(answer.join("\n").trim());

  process.exit();
});