• https://www.acmicpc.net/problem/17825

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(" ")
  .map(Number);

const point = [
  0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40,
  13, 16, 19, 22, 24, 25, 26, 27, 28, 30, 35, 0,
];

const next = [
  [1, 2, 3, 4, 5],
  [2, 3, 4, 5, 6],
  [3, 4, 5, 6, 7],
  [4, 5, 6, 7, 8],
  [5, 6, 7, 8, 9],
  [21, 22, 23, 26, 30],
  [7, 8, 9, 10, 11],
  [8, 9, 10, 11, 12],
  [9, 10, 11, 12, 13],
  [10, 11, 12, 13, 14],
  [24, 25, 26, 30, 31],
  [12, 13, 14, 15, 16],
  [13, 14, 15, 16, 17],
  [14, 15, 16, 17, 18],
  [15, 16, 17, 18, 19],
  [29, 28, 27, 26, 30],
  [17, 18, 19, 20, 32],
  [18, 19, 20, 32, 32],
  [19, 20, 32, 32, 32],
  [20, 32, 32, 32, 32],
  [32, 32, 32, 32, 32],
  [22, 23, 26, 30, 31],
  [23, 26, 30, 31, 20],
  [26, 30, 31, 20, 32],
  [25, 26, 30, 31, 20],
  [26, 30, 31, 20, 32],
  [30, 31, 20, 32, 32],
  [26, 30, 31, 20, 32],
  [27, 26, 30, 31, 20],
  [28, 27, 26, 30, 31],
  [31, 20, 32, 32, 32],
  [20, 32, 32, 32, 32],
  [32, 32, 32, 32, 32],
];

let max = 0;

for (let i = 0; i < 4; i++) {
  move(i, 0, [0, 0, 0, 0], 0);
}

console.log(max);
function move(unit, cnt, location, score) {
  if (cnt == 10) {
    max = Math.max(max, score);
    return;
  }

  const nowLocation = location[unit];
  if (nowLocation == 32) {
    return;
  }

  const nextLocation = next[nowLocation][input[cnt] - 1];

  if (location.filter((v) => v != 32).includes(nextLocation)) {
    return;
  } else {
    const newLocation = [...location];
    newLocation[unit] = nextLocation;
    const newScore = score + point[nextLocation];
    for (let i = 0; i < 4; i++) {
      move(i, cnt + 1, newLocation, newScore);
    }
  }
}

역시 개인적으로 제대로 풀고 싶었는데,,,, 기말이라 벼락치기하느라 제대로 못 풀었다,,,,

풀이 코드를 보고 해결한 대신, 기말 이후에 다시 한 번 더 풀어볼 예정!

마지막 TIL인데 아쉽당

• https://school.programmers.co.kr/learn/courses/30/lessons/150370

코드

const changeToDate = (year, month, date) => {
  return +year * 12 * 28 + +month * 28 + +date;
};

function solution(today, terms, privacies) {
  var answer = [];

  const termsObj = {};
  for (const info of terms) {
    const [type, month] = info.split(' ');
    termsObj[type] = changeToDate(0, month, 0);
  }

  const todayDate = changeToDate(...today.split('.'));

  for (let i = 0; i < privacies.length; i++) {
    const [date, type] = privacies[i].split(' ');
    const dueDate = changeToDate(...date.split('.')) + termsObj[type] - 1;

    if (todayDate > dueDate) answer.push(i + 1);
  }

  return answer;
}

개인적으로 제대로 풀고 싶었는데,,,, 내일이 기말이라 벼락치기하느라 제대로 못 풀었다,,ㅠ (변명일수도)

풀이 코드를 보고 해결한 대신, 기말 이후에 다시 한 번 더 풀어볼 예정!

• https://school.programmers.co.kr/learn/courses/30/lessons/72410?language=javascript

코드

구글링 및 풀이 참고..

function solution(new_id) {
    const answer = new_id
        .toLowerCase()
        .replace(/[^\w-_.]/g, '')
        .replace(/\.+/g, '.')
        .replace(/^\.|\.$/g, '')
        .replace(/^$/, 'a')
        .slice(0, 15).replace(/\.$/, '');
    const len = answer.length;
    return len > 2 ? answer : answer + answer.charAt(len - 1).repeat(3 - len);
}

• https://www.acmicpc.net/problem/11054

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [N, input] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const arr = input.split(" ").map((i) => +i);

const inDP = new Array(N).fill(1);
const deDP = new Array(N).fill(1);

for (let i = 0; i < N; i += 1) {
  let cnt = 1;
  for (let j = 0; j < i; j += 1) {
    if (arr[i] > arr[j]) cnt = Math.max(cnt, inDP[j] + 1);
  }
  inDP[i] = cnt;
}

for (let i = N - 1; i >= 0; i -= 1) {
  let cnt = 1;
  for (let j = i + 1; j < N; j += 1) {
    if (arr[i] >  arr[j]) cnt = Math.max(cnt, deDP[j] + 1);
  }
  deDP[i] = cnt;
}

console.log(Math.max(...inDP.map((v, i) => v + deDP[i])) - 1);

• https://www.acmicpc.net/problem/2631

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [N, ...arr] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);

const longest = new Array(N).fill(1);

for (let i = 1; i < N; i += 1) {
  let cnt = 0;
  for (let j = 0; j < i; j += 1) {
    if (arr[j] < arr[i]) cnt = Math.max(cnt, longest[j]);
  }
  longest[i] = cnt + 1;
}

console.log(N - Math.max(...longest));

• https://www.acmicpc.net/problem/1965

코드

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

const N = Number(input[0]);
const boxes = input[1].split(" ").map(Number);

function returnMaxBox(len, boxes) {
  const dp = new Array(len).fill(1);

  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      if (boxes[j] < boxes[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }

  return Math.max(...dp);
}

console.log(returnMaxBox(N, boxes));

• https://www.acmicpc.net/problem/9461

코드

const filepath = process.platform === 'linux' ? 0 : './input.txt';
const [N, ...input] = require('fs')
  .readFileSync(filepath)
  .toString()
  .trim()
  .split('\n');

const dp = new Array(101).fill(1);

dp[4] = 2;
dp[5] = 2;

for (let i = 6; i <= 100; i++) {
  dp[i] = dp[i - 1] + dp[i - 5];
}

for (const n of input) {
  console.log(dp[Number(n)]);
}

• https://www.acmicpc.net/problem/11055

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [N, input] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const nums = input.split(" ").map(Number);
const memo = new Array(N).fill(0);

for (let i = 0; i < N; i++) {
  let max = 0;
  let maxIdx = -1;

  for (let j = 0; j < i; j++) {
    if (nums[i] > nums[j] && memo[j] > max) {
      max = memo[j];
      maxIdx = j;
    }
  }
  memo[i] = maxIdx === -1 ? nums[i] : nums[i] + memo[maxIdx];
}

console.log(Math.max(...memo));

• https://acmicpc.net/problem/11722

코드

const file = process.platform === 'linux' ? 0 : './input.txt';
const [N, input] = require('fs')
  .readFileSync(file)
  .toString()
  .trim()
  .split('\n');

let inputs = input.split(' ').map((v) => Number(v));
let dp = [];

for (let i = 0; i < N; i++) {
  let max = 0;
  for (let j = 0; j < i; j++) {
    if (inputs[i] < inputs[j] && dp[j] > max) max = dp[j];
  }
  dp[i] = max + 1;
}

console.log(Math.max(...dp));

• https://www.acmicpc.net/problem/9655

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = +require("fs").readFileSync(filePath).toString().trim();

input % 2 === 0 ? console.log("CY") : console.log("SK");

• https://www.acmicpc.net/problem/2116

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require("fs").readFileSync(filePath).toString().split("\n");
const N = Number(input.shift());
const dice = input.map((r) => r.split(" ").map(Number));
const facToFace = {
  0: 5,
  1: 3,
  2: 4,
  3: 1,
  4: 2,
  5: 0,
};

let max = 0;

const dfs = (diceIdx, topNum, sum) => {
  if (diceIdx === N) {
    max = Math.max(sum, max);
    return;
  }
  const bottom = dice[diceIdx].findIndex((v) => v === topNum);
  const top = facToFace[bottom];

  const maxNum = Math.max(
    ...dice[diceIdx].filter((_, i) => i !== bottom && i !== top)
  );
  dfs(diceIdx + 1, dice[diceIdx][top], sum + maxNum);
};

(function () {
  dice[0].forEach((_, i) => {
    const bottom = i;
    const top = facToFace[bottom];

    const maxNum = Math.max(
      ...dice[0].filter((_, i) => i !== bottom && i !== top)
    );
    dfs(1, dice[0][top], maxNum);
  });
  console.log(max);
})();

• https://school.programmers.co.kr/learn/courses/30/lessons/86971

오늘의 학습 키워드

BFS

• 정점과 같은 레벨에 있는 노드(형제 노드)를 먼저 탐색하는 방식
• 큐 자료구조를 사용하여 인접한 정점들의 리스트를 관리한다

코드

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }
  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex += 1;
  }
  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex += 1;
    return item;
  }
  peek() {
    return this.items[this.headIndex];
  }
  get length() {
    return this.tailIndex - this.headIndex;
  }
  get isEmpty() {
    return this.length === 0;
  }
}

function solution(n, wires) {
  let answer = Number.MAX_SAFE_INTEGER;

  // G (graph)
  const G = Array.from(new Array(n + 1), () => []);

  wires.forEach(([u, v]) => {
    G[u].push(v);
    G[v].push(u);
  });

  // BFS
  const bfs = (start, target) => {
    const visited = Array(n + 1).fill(false);
    const Q = new Queue();
    let count = 0;

    Q.enqueue([start]);
    visited[start] = true;

    while (!Q.isEmpty) {
      let w = Q.dequeue();
      G[w].forEach((next) => {
        if (next !== target && visited[next] === false) {
          visited[next] = true;
          Q.enqueue([next]);
        }
      });
      count += 1;
    }

    return count;
  };

  wires.forEach((next) => {
    let [u, v] = next;
    answer = Math.min(answer, Math.abs(bfs(u, v) - bfs(v, u)));
  });

  return answer;
}

• https://school.programmers.co.kr/learn/courses/30/lessons/42839

코드

// 소수 판별하기
function isPrime(n) {
  if (n < 2) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

// 순열 - 만들 수 있는 모든 경우의 수 추출하기
const getNumbers = (arr, len) => {
  if (len === 1) return arr.map((v) => [v]);

  const result = [];

  arr.forEach((f, i, o) => {
    const rest = [...o.slice(0, i), ...o.slice(i + 1)];
    const cases = getNumbers(rest, len - 1);
    const newCases = cases.map((v) => [f, ...v]);
    result.push(...newCases);
  });

  return result;
};

const getAllNumbers = (arr) => {
  let results = [];
  arr.forEach((_, i, o) => results.push(...getNumbers(o, i + 1)));

  return results;
};

function solution(numbers) {
  const output = getAllNumbers([...numbers]);
  const createdNumbers = output.map((v) =>
    v.length === 1 ? Number(v) : Number(v.join(""))
  );
  const filteredNumbers = createdNumbers.filter(
    (v, i) => createdNumbers.indexOf(v) === i && isPrime(v)
  );
  return filteredNumbers.length;
}

• https://school.programmers.co.kr/learn/courses/30/lessons/87946

오답노트

• 모든 상황을 고려했는가
  • 완전탐색이라면서 그리디로 풀지는 않았는지,,,ㅎ
  • 그래서 정확도가 떨어지지 않았는지,,,,

코드

function makeAllCase(arr, len) {
  if (len === 1) return arr.map((v) => [v]);

  const result = [];

  arr.forEach((f, i, o) => {
    const rest = [...o.slice(0, i), ...o.slice(i + 1)];
    const cases = makeAllCase(rest, len - 1);
    const newCases = cases.map((el) => [f, ...el]);
    result.push(...newCases);
  });

  return result;
}

function solution(k, dungeons) {
  let maxCount = 0;
  const allCases = makeAllCase(dungeons, dungeons.length);

  allCases.forEach((cases) => {
    let currentK = k;
    let count = 0;

    for (const [r, m] of cases) {
      if (currentK >= r) {
        currentK -= m;
        count += 1;
      }
    }

    maxCount = Math.max(maxCount, count);
  });

  return maxCount;
}

실패했던 코드

function solution(k, dungeons) {
  let cnt = 0;
  const copy = dungeons.slice(0).sort((a, b) => b[0] - a[0]);

  while (copy.length > 0) {
    const [r, u] = copy[0];
    if (k < r) break;

    if (k === r) {
      copy.shift();
      k -= u;
    } else {
      const [, mu] = copy.sort((a, b) => a[1] - b[1]).shift();
      k -= mu;
    }
    cnt += 1;
  }

  return cnt;
}

• https://school.programmers.co.kr/learn/courses/30/lessons/42842

코드

function solution(brown, yellow) {
  const total = brown + yellow;

  for (let h = 3; h <= Math.sqrt(total); h += 1) {
    if (total % h === 0) {
      const w = total / h;

      if ((w - 2) * (h - 2) === yellow) {
        return [w, h];
      }
    }
  }
}

• https://school.programmers.co.kr/learn/courses/30/lessons/42840

코드

function solution(answers) {
  const patterns = ["12345", "21232425", "3311224455"];
  const scores = patterns.map(
    (p) => answers.filter((a, i) => a == p[i % p.length]).length
  );
  const maxScore = Math.max(...scores);

  return scores.map((s, i) => (s === maxScore ? i + 1 : null)).filter(Boolean);
}

• https://www.acmicpc.net/problem/1374

오늘의 학습 키워드

우선순위 큐(Priority Queue)

• 우선순위에 따라서 데이터를 추출하는 자료구조
• 컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용
• 일반적으로 힙(heap)을 이용해 구현한다

힙(Heap)

• 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조
• 최대 힙(max heap) : 값이 큰 원소부터 추출
• 최소 힙(min heap) : 값이 작은 원소부터 추출
• 힙은 원소의 삽입과 삭제를 위해 O(logN)의 수행 시간을 요구
• 단순한 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일
• 이 경우 시간 복잡도는 O(NlogN)

코드

const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map(Number));

class MinHeap {
  #arr;

  constructor(els) {
    this.#arr = els ?? [];
  }

  enq(el) {
    this.#arr.push(el);

    let curIdx = this.#arr.length - 1;
    let parIdx = Math.floor((curIdx - 1) / 2);

    while (curIdx > 0 && this.#arr[parIdx] > this.#arr[curIdx]) {
      this._swap(curIdx, parIdx);
      curIdx = parIdx;
      parIdx = Math.floor((curIdx - 1) / 2);
    }
  }

  deq() {
    if (this.#arr.length === 0) return null;
    if (this.#arr.length === 1) return this.#arr.pop();

    const originRoot = this.#arr[0];
    this.#arr[0] = this.#arr.pop();
    let curIdx = 0;

    while (curIdx * 2 + 1 < this.#arr.length) {
      let childIdx =
        curIdx * 2 + 2 < this.#arr.length &&
        this.#arr[curIdx * 2 + 2] < this.#arr[curIdx * 2 + 1]
          ? curIdx * 2 + 2
          : curIdx * 2 + 1;

      if (this.#arr[curIdx] < this.#arr[childIdx]) {
        break;
      }

      this._swap(curIdx, childIdx);
      curIdx = childIdx;
    }
    return originRoot;
  }

  _swap(a, b) {
    const tmp = this.#arr[a];
    this.#arr[a] = this.#arr[b];
    this.#arr[b] = tmp;
  }

  get size() {
    return this.#arr.length;
  }

  get peek() {
    return this.#arr[0];
  }
}

const minHeap = new MinHeap();

const sorted = arr.sort((a, b) => a[1] - b[1]);

sorted.forEach(([_, s, t]) => {
  if (minHeap.size === 0) minHeap.enq(t);
  else {
    const head = minHeap.peek;
    if (s >= head) minHeap.deq();
    minHeap.enq(t);
  }
});

console.log(minHeap.size);

최소힙 자체는 구현한 경험이 있어서, 문제 해결 방법을 캐치한 후에는 빠르게 풀 수 있었다.

• https://www.acmicpc.net/problem/2212

코드

const file = process.platform === 'linux' ? 0 : './input.txt';
const [n, k, ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number))
  .flat();

const sensors = inputs.sort((a, b) => a - b);

let diff = [];
for (let i = 1; i < n; i++) {
  diff.push(sensors[i] - sensors[i - 1]);
}

diff = diff.sort((a, b) => a - b).filter((it) => it !== 0);

for (let i = 0; i < k - 1; i++) {
  if (diff.length > 0) diff.pop();
}

if (diff.length === 0) console.log(0);
else console.log(diff.reduce((pre, cur) => pre + cur));

• https://www.acmicpc.net/problem/31926

코드

const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
let N = +require("fs").readFileSync(filePath).toString().trim();

const DALDIDALGO = 8; // (d)(a)(l)(d)(i)(dal)(g)(o)
const DALDIDAN = 2; // (daldida)(n)

let cnt = 0;

let exponent = Math.floor(Math.log2(N));
N -= 2 ** exponent;
cnt += exponent;

console.log(DALDIDALGO + cnt + DALDIDAN);

비비.. 밤양갱이... 백준 코테 문제로 희생되다니..🫢

• https://www.acmicpc.net/problem/2847

코드

const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
let [N, ...scores] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map(Number);

let cnt = 0;

for (let i = N - 1; i > 0; i -= 1) {
  if (scores[i - 1] >= scores[i]) {
    cnt += scores[i - 1] - scores[i] + 1;
    scores[i - 1] = scores[i] - 1;
  }
}

console.log(cnt);