구름 코테 8주차

// Run by Node.js
const readline = require('readline');

(async () => {
  let rl = readline.createInterface({ input: process.stdin });

  const inputs = [];

  rl.on('line', (line) => inputs.push(line)).on('close', () => {
    main(+inputs[0], inputs[1]);
    process.exit();
  });
})();

function main(N, S) {
  let result = '';
  const goormNums = {
    qw: 1,
    as: 2,
    zx: 3,
    we: 4,
    sd: 5,
    xc: 6,
    er: 7,
    df: 8,
    cv: 9,
    ze: 0,
  };

  for (let i = 0; i < N - 1; i += 1) {
    const now = S[i] + S[i + 1];

    if (now in goormNums) {
      result += goormNums[now];
    }
  }

  console.log(result);
}

// Run by Node.js
const readline = require('readline');

(async () => {
  let rl = readline.createInterface({ input: process.stdin });

  const inputs = [];

  rl.on('line', (line) => inputs.push(line)).on('close', () => {
    main(+inputs[0], inputs[1].trim().split(' ').map(Number));
  });
})();

function main(N, arr) {
  let resultArr = new Array(N).fill(0);

  const stack = [];

  arr.forEach((v, idx) => {
    if (!idx) return stack.push(v);

    resultArr[idx] = stack.length;

    while (stack[stack.length - 1] <= v) {
      stack.pop();
    }

    stack.push(v);
  });

  console.log(resultArr.join(' '));
}

// Run by Node.js
const readline = require('readline');

(async () => {
  let rl = readline.createInterface({ input: process.stdin });
  const inputs = [];

  rl.on('line', (line) => inputs.push(line)).on('close', () => {
    main(+inputs[0], inputs[1].trim().split(' ').map(Number));
    process.exit();
  });
})();

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  heappush(val) {
    this.heap.push(val);

    let nowIndex = this.heap.length - 1;
    let parentIndex = Math.floor(nowIndex / 2);

    while (nowIndex > 1 && this.heap[nowIndex] > this.heap[parentIndex]) {
      this.swap(nowIndex, parentIndex);

      nowIndex = parentIndex;
      parentIndex = Math.floor(nowIndex / 2);
    }
  }

  heappop() {
    if (this.heap.length === 1) return;
    if (this.heap.length === 2) return this.heap.pop();

    const min = this.heap[1];
    this.heap[1] = this.heap.pop();

    let [nowIndex, leftIndex, rightIndex] = [1, 2, 3];

    if (this.heap[leftIndex] === undefined) {
      return min;
    }

    if (this.heap[rightIndex] === undefined) {
      if (this.heap[leftIndex] > this.heap[nowIndex]) {
        this.swap(leftIndex, nowIndex);

        return min;
      }
    }

    while (
      this.heap[leftIndex] > this.heap[nowIndex] ||
      this.heap[rightIndex] > this.heap[nowIndex]
    ) {
      const minIndex =
        this.heap[leftIndex] < this.heap[rightIndex] ? rightIndex : leftIndex;

      this.swap(nowIndex, minIndex);

      nowIndex = minIndex;
      leftIndex = nowIndex * 2;
      rightIndex = nowIndex * 2 + 1;
    }

    return min;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  head() {
    return this.heap[1];
  }

  get length() {
    return this.heap.length - 1;
  }
}

function main(N, A) {
  let total = BigInt(0);

  const map = new Map();
  const maxHeap = new MaxHeap();

  A.forEach((v) => {
    if (map.has(v)) {
      map.delete(v);

      maxHeap.heappush(v);
    } else {
      map.set(v, 1);
    }
  });

  while (maxHeap.length >= 2) {
    const a = maxHeap.heappop();
    const b = maxHeap.heappop();

    total += BigInt(a * b);
  }

  console.log(total.toString());
}

1. 결국 핵심은, DP로 해주는 것이었는데, 자바스크립트에서는 배열로 할 시 런타임에러가 나와버린다. 해결 방법으로는… 배열 대신 Set을 써주는 방법으로 했는데, 이마저도 시간초과가 나왔다. 생각보다 Set 자료구조가 공간 복잡도가 크다는 것을 알게 됐다. 따라서 [N][K]로 배열을 구성하지 않고 [K][N]으로 구성해서, Set의 저장 크기를 작게 만들어주어 문제를 해결했다.

// Run by Node.js
const readline = require('readline');

(async () => {
  let rl = readline.createInterface({ input: process.stdin });

  const inputs = [];

  rl.on('line', (line) => inputs.push(line)).on('close', () => {
    const [N, K] = inputs[0].split(' ').map(Number);
    const graph = {};

    for (let i = 1; i < N; i += 1) {
      const [a, b] = inputs[i].split(' ').map(Number);

      graph[a] = graph[a] ? [...graph[a], b] : [b];
      graph[b] = graph[b] ? [...graph[b], a] : [a];
    }

    const A = [0, ...(inputs[inputs.length - 1].split(' ').map(Number) ?? [])];

    main(N, K, graph, A);
  });
})();

function main(N, K, G, A) {
  let result = 0;

  const dp = Array.from({ length: K + 1 }, () => new Set());
  dp[0].add(0);

  const DPS = (cur, prev) => {
    for (let i = 0; i < K + 1; i += 1) {
      if (dp[i].has(prev)) {
        dp[i].add(cur);

        const nowCap = i + A[cur];
        if (nowCap <= K) {
          dp[nowCap].add(cur);

          result = Math.max(result, nowCap);
        }
      }
    }

    if (G[cur]) {
      for (const nxt of G[cur]) {
        if (nxt !== prev) {
          DPS(nxt, cur);
        }
      }
    }
  };

  DPS(1, 0);

  console.log(result);
}