백준 알고리즘 어려웠던 점 모음

두배열 합치기

sort

는 시간복잡도가 NlogN이다.

그래서 곱하기로 가는 것보다 더하기로 가는 것이 더 효율적이다.

const input = require("fs")
  .readFileSync("20230403/example.txt")
  .toString()
  .trim()
  .split("\n");

let num1 = Number(input[0]);
let num2 = Number(input[2]);
let first = input[1].split(" ").map(Number);
let second = input[3].split(" ").map(Number);
let result = [];
// let result = [...first, ...second];

let j = 0;
let i = 0;

while (true) {
  if (num1 - 1 === i || num2 - 1 === j) {
    result = [...result, ...first.slice(i), ...second.slice(j)];
    break;
  }

  if (first[i] < second[j]) {
    result.push(first[i]);

    i++;
  } else {
    result.push(second[j]);

    j++;
  }
  console.log(first[i], second[j], result);
}
console.log(result);
// console.log(result.sort((a, b) => a - b));

문자열 폭팔

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

const input = require("fs")
  .readFileSync("20230404/example1.txt")
  .toString()
  .trim()
  .split("\n");
const log = console.log;

const solution1 = (input) => {
  const [string, target] = input;
  const targetL = target.length;
  const stack = [];
  for (let i = 0; i < string.length; i++) {
    stack.push(string[i]);
    log(-targetL, targetL);
    while (targetL <= stack.length) {
      const temp = stack.slice(-targetL).join("");
      if (temp === target) stack.splice(-targetL, targetL);
      else break;
    }
  }
  log(stack.length > 0 ? stack.join("") : "FRULA");
};

solution1(input);
//하나씩 하나씩 넣어줌

//replace, split은 용량이 크다.
//replace는 안뱉음
//수가 줄어듬

깨달은 점 stack은 앞 문자열부터 하나씩 넣고 뒤에서부터 검사한다.
이때 slice로 뒤에서부터 검사하며 확인하는 것이다.

splice는 시작할 인덱스와 번호만큼을 빼준다. splice도 시간이 많이 걸려서 다른 방법이 또 있었다.

2번째
맨 뒤 문자열을 확인해서 지우는 방식으로 푼다.

const input = require("fs")
  .readFileSync("20230404/example1.txt")
  .toString()
  .trim()
  .split("\n");
const log = console.log;

const solution2 = (input) => {
  const [string, target] = input;
  const targetL = target.length;
  const stack = [];

  for (let i = 0; i < string.length; i++) {
    if (target[targetL - 1] === string[i]) {
      let flag = true;
      for (let j = 1; j < targetL; j++) {
        if (target[targetL - 1 - j] !== stack[stack.length - j]) {
          flag = false;

          stack.push(string[i]); //같긴하나 달라서 넣어줌
          break;
        }
      }
      if (flag) {
        // 안넣어줬으니 애들을 빼줌
        let count = targetL - 1;
        while (count--) stack.pop();
      }
    } else {
      //일단 다르면 넣어줌

      stack.push(string[i]);
    }
  }

  log(stack.length > 0 ? stack.join("") : "FRULA");
};
solution2(input);
//하나씩 하나씩 넣어줌

부분집합 만들기

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

const [N, S, ...arr] = require("fs")
  .readFileSync("20230404/example3.txt")
  .toString()
  .trim()
  .split(/\s+/)
  .map(Number);
//5 , 0
const solve = (N, S, arr) => {
  let output = 0;
  const recursion = (i, sum) => {
    if (i === N) return;

    sum += arr[i];
    if (sum === S) output++;

    recursion(i + 1, sum);
    recursion(i + 1, sum - arr[i]);
  };

  recursion(0, 0);
  console.log(output);
};

solve(N, S, arr);

하나를 넣고 하나를 빼는 방법으로 모든 경우의수를 작성하고
재귀로 처리한다.

순열 관리하기

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

const input = require("fs")
  .readFileSync("20230404/example2.txt")
  .toString()
  .trim()
  .split("\n");
const log = console.log;

let s = [];
let answer = -1;

function check(s, b, n) {
  s = Number(s.join(""));
  if (s.toString().length !== n) return -1;
  if (s < b && s > answer) answer = s;
}

function sol(A, b, visited) {
  console.log(A, s, visited);
  if (s.length === A.length) return check(s, b, A.length);

  for (let i = 0; i < A.length; i++) {
    if (!visited[i]) {
      s.push(A[i]);
      visited[i] = true;
      sol(A, b, visited);

      s.pop();

      visited[i] = false;
    }
  }
}

//T,T,T,T
//

function insert() {
  const input = [1234, 3456];
  let [a, b] = input.slice(0, 2);
  let A = a.toString().split("").map(Number);
  //console.log(A)
  let visited = new Array(A.length).fill(false);
  sol(A, b, visited);
  console.log(answer);
}
insert();

배열로 방문한 것을 확인하고 순차적으로 값이 들어갈 수 있도록 재귀와 배열을 확인한다.

트리 순회

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

전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

const fs = require("fs");
let inputData = fs
  .readFileSync("20230404/example5.txt")
  .toString()
  .trim()
  .split("\n");
let tree = {};
for (let i = 1; i < inputData.length; i++) {
  let input = inputData[i].trim().split(" ");
  tree[input[0]] = [input[1], input[2]]; //부모 노드를 key 값으로 자식 노드를 value 값으로 저장.
}
let answel = "";

preOrder("A"); //항상 A는 루트 노드가 됨.
answel += "\n";

inOrder("A");
answel += "\n";

postOrder("A");

function preOrder(pn) {
  //전위 순회
  if (pn === ".") {
    //재귀의 종료 조건
    return;
  }
  let [lcn, rcn] = tree[pn]; //왼쪽 자식 노드, 오른쪽 자식 노드
  answel += pn;
  preOrder(lcn);
  preOrder(rcn);
}

function inOrder(pn) {
  //중위 순회
  if (pn === ".") {
    //재귀의 종료 조건
    return;
  }
  let [lcn, rcn] = tree[pn]; //왼쪽 자식 노드, 오른쪽 자식 노드
  inOrder(lcn);
  answel += pn;
  inOrder(rcn);
}

function postOrder(pn) {
  //후위 순회
  if (pn === ".") {
    //재귀의 종료 조건
    return;
  }
  let [lcn, rcn] = tree[pn]; //왼쪽 자식 노드, 오른쪽 자식 노드
  postOrder(lcn);
  postOrder(rcn);
  answel += pn;
}

console.log(answel);

https://ingong.github.io/PS/BOJ%209935%20%EB%AC%B8%EC%9E%90%EC%97%B4%20%ED%8F%AD%EB%B0%9C/