백준 - 04

17413번 - 단어 뒤집기 2

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

• 알파벳 소문자(‘a’-‘z’), 숫자(‘0’-‘9’), 공백(‘ ‘), 특수 문자(‘<’, ‘>’)로만 이루어져 있다.
• 문자열의 시작과 끝은 공백이 아니다.
• ’<’와 ‘>’가 문자열에 있는 경우 번갈아가면서 등장하며, ‘<’이 먼저 등장한다. 또, 두 문자의 개수는 같다.

태그는 ‘<’로 시작해서 ‘>’로 끝나는 길이가 3 이상인 부분 문자열이고, ‘<’와 ‘>’ 사이에는 알파벳 소문자와 공백만 있다.

단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다.

태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

---

첫 풀이

• 스택 활용

입력받은 문자열을 하나씩 스택에 넣으며 조건에 따라 태그는 그대로, 문자는 뒤집어서 출력합니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim().split("");

// 스택 생성
let stack = [];

// 출력 문자열
let answer = "";

// 태그인지 판멸, 태그라면 그대로 출력
let isTag = true;

for (let x of input) {
  if (x == ">") {
    // 태그 끝 부분, 정상 출력
    isTag = true;
    stack.push(x);
    answer += stack.join("");
    stack = [];
  } else if (x == "<") {
    // 태그 시작 부분,
    isTag = false;
    if (stack.length) answer += stack.reverse().join("");
    stack = [];
    stack.push(x);
  } else if (isTag && x == " ") {
    // 태그 밖일 때 공백을 기준으로 뒤집어서 출력
    answer += stack.reverse().join("") + " ";
    stack = [];
  } else {
    stack.push(x);
  }
}

// 마지막 문자가 스택에 남아있다면 뒤집어서 출력
if (stack.length) answer += stack.reverse().join("");

console.log(answer);

---

두번째 풀이

정규표현식을 이용한 풀이입니다.

const input = `${require("fs").readFileSync("dev/stdin")}`.trim();
// 태그와 문자를 정규표현식으로 걸러냅니다.
const regex = /<[a-z\s]+>|[a-z0-9]+/g;

// replace 메서드로 정규표현식으로 걸러낸 문자열을 변경합니다.
const answer = input.replace(regex, (w) => {
  // '<'로 시작하는(즉, 태그는) 정상 출력, 문자는 뒤집어서 출력합니다.
  return w.startsWith("<") ? w : w.split("").reverse().join("");
});

console.log(answer);

---

오등큰수

크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.
그러한 수가 없는 경우에 오등큰수는 -1이다.

예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다.
NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

---

풀이

Map 객체에 값의 갯수를 저장합니다.
스택에 인덱스를 담아 조건에 맞을 떄 pop해서 answer 값을 변경합니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

let n = +input[0];
let arr = input[1].split(" ").map(Number);
let map = new Map();

// 값의 갯수 저장
for (let x of arr) {
  map.set(x, map.get(x) ? map.get(x) + 1 : 1);
}

let stack = [];
let answer = new Array(n).fill(-1);

for (let i = 0; i < n; i++) {
  while (stack.length && map.get(arr[stack.at(-1)]) < map.get(arr[i])) {
    answer[stack.pop()] = arr[i];
  }

  stack.push(i);
}

console.log(answer.join(" "));

---

후위 표기식

후위 표기법은 연산자가 피연산자 뒤에 위치하는 방법이다.
이 방법의 장점은 다음과 같다.
우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다.
또한 같은 방법으로 괄호 등도 필요 없게 된다.
예를 들어 a+bc를 후위 표기식으로 바꾸면 abc+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다.
우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다.
그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+bc는 (a+(bc))의 식과 같게 된다.
그 다음에 안에 있는 괄호의 연산자 를 괄호 밖으로 꺼내게 되면 (a+bc)가 된다.
마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

풀이

연산자를 저장할 스택을 생성합니다.

연산자의 우선순위를 고려해 조건문으로 나눠 answer에 연산자를 추가합니다.

우선순위

• (, )
• *, /
• +, -

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim().split("");

let operator = [];
let answer = "";

for (let x of input) {
  if (x == "+" || x == "-") {
    // 저장된 연산자들을 입력, 괄호가 시작됐다면 괄호 안까지만 입력합니다.
    while (operator.length > 0 && operator.at(-1) !== "(") {
      answer += operator.pop();
    }

    operator.push(x);
  } else if (x == "*" || x == "/") {
    // 저장된 연산자들을 입력
    // 덧셈과 뺄셈은 우선순위가 낮으므로 입력하지 않습니다.
    while (
      operator.length > 0 &&
      (operator.at(-1) == "*" || operator.at(-1) == "/")
    ) {
      answer += operator.pop();
    }

    operator.push(x);
  } else if (x == "(") {
    operator.push(x);
  } else if (x == ")") {
    // 괄호가 끝난다면 괄호 시작까지 저장된 연산자들 입력합니다.
    while (operator.at(-1) !== "(") {
      answer += operator.pop();
    }

    // 입력이 끝나면 '('를 pop 해줍니다.
    operator.pop();
  } else {
    // 피연산자는 바로 입력
    answer += x;
  }
}

while (operator.length) {
  answer += operator.pop();
}

console.log(answer);

---

후위 표기식2

후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.

---

풀이

Map 객체에 피연산자를 key, 대응하는 값을 value로 저장합니다.

입력받은 후위 표기식의 앞에서 부터 stack에 저장하며 연산자가 나오면 pop을 두번해 연산한후 다시 push합니다.

피연산자는 map.get(key)로 값을 받아 Number형태로 저장합니다.

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";

let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

let [n, arr, ...nums] = input;
nums = nums.map(Number);

let charcode = "A".charCodeAt();
let map = new Map();

// 피연산자 값 저장
for (let i = 0; i < n; i++) {
  let key = String.fromCharCode(charcode + i);
  map.set(key, Number(nums[i]));
}

let stack = [];
let [a, b] = [0, 0];

for (let x of arr) {
  switch (x) {
    case "+":
      [a, b] = [stack.pop(), stack.pop()];
      stack.push(a + b);
      break;

    case "-":
      [a, b] = [stack.pop(), stack.pop()];
      stack.push(b - a);
      break;

    case "*":
      [a, b] = [stack.pop(), stack.pop()];
      stack.push(a * b);
      break;

    case "/":
      [a, b] = [stack.pop(), stack.pop()];
      stack.push(b / a);
      break;

    default:
      // 저장시 대응하는 값을 Number로 저장
      let number = map.get(x);
      stack.push(number);
  }
}

console.log(stack[0].toFixed(2));