Homile

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

11
6
1 3
1 8
7
8
3
2 5
1 2
5
4
4

1
8
3
8
3
5
3

문제풀이(1)

위의 데크로직을 구현하면 되는 문제이다. 시간이 다소 소요됐다.

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

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  unshift(value) {
    // 정수 X를 덱의 앞에 넣는다.
    const node = new Node(value);
    if (!this.head) {
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
    }
    this.head = node;
    this.size++;
  }

  push(value) {
    // 정수 X를 덱의 뒤에 넣는다.
    const node = new Node(value);
    if (!this.tail) {
      this.head = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
    }
    this.tail = node;
    this.size++;
  }

  shift() {
    // 맨 앞의 정수를 빼고 출력한다.
    if (!this.head) {
      return -1;
    }
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null;
    }
    this.size--;
    return value;
  }

  pop() {
    // 맨 뒤의 정수를 빼고 출력한다.
    if (!this.tail) {
      return -1;
    }
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null;
    } else {
      this.head = null;
    }
    this.size--;
    return value;
  }

  length() {
    // 덱에 들어있는 정수의 개수를 출력한다.
    return this.size;
  }

  isEmpty() {
    // 덱이 비어있으면 1, 아니면 0을 출력한다.
    return this.size === 0 ? 1 : 0;
  }

  getFront() {
    // 덱에 정수가 있다면 맨 앞의 정수를 출력한다.
    return this.head ? this.head.value : -1;
  }

  getBack() {
    // 덱에 정수가 있다면 맨 뒤의 정수를 출력한다.
    return this.tail ? this.tail.value : -1;
  }
}

const deque = new Deque();

let answer = "";

for (let i = 0; i < N; i++) {
  const [command, value] = input[i].split(" ").map(Number);

  // unshift, push, shift, pop, length, isEmpty, getFront, getBack
  switch (command) {
    case 1:
      deque.unshift(value);
      break;
    case 2:
      deque.push(value);
      break;
    case 3:
      answer += `${deque.shift()}\n`;
      break;
    case 4:
      answer += `${deque.pop()}\n`;
      break;
    case 5:
      answer += `${deque.length()}\n`;
      break;
    case 6:
      answer += `${deque.isEmpty()}\n`;
      break;
    case 7:
      answer += `${deque.getFront()}\n`;
      break;
    case 8:
      answer += `${deque.getBack()}\n`;
      break;
    default:
      break;
  }
}

console.log(answer.trim());

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

3 1

1
2
3

4 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

자신과 같거나 방문했던 노드는 선택하지 않는 점에서 DFS로 풀어야 한다고 생각했다.
찾아보니 이와 같은 문제를 백트래킹 문제라고 한다.

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

let result = "";
const answer = [];
const visited = new Array(N).fill(false);

const dfs = (count) => {
  if (count === M) {
    return (result += `${answer.join(" ")}\n`);
  }

  for (let i = 0; i < N; i++) {
    if (!visited[i]) {
      visited[i] = true;
      answer.push(i + 1);
      dfs(count + 1);
      answer.pop();
      visited[i] = false;
    }
  }
};

dfs(0);

console.log(result.trim());

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

122333444455555

11060446

문제풀이(1)

처음엔 간단하게 Math.sqrt를 사용해서 제곱근을 구하면 될 것이라 생각해서 풀어보았다.

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

// 제곱근을 찾는다.
let result = Math.floor(Math.sqrt(n));

// 제곱근보다 작을 경우 +1을 해준다.
console.log(result ** 2 < n ? result + 1 : result);

문제풀이(2)

이진 탐색으로 푸는 방법이 있다고하여 구현해보았다.

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

const binarySearch = (num) => {
  let low = 0;
  let high = num;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (mid * mid < num) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return low;
};

console.log(binarySearch(n));

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

2

1

10

3

문제풀이(1)

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
위의 공식을 실행하면 된다. 횟수를 카운트해서 출력한다.
하지만, 10^6승의 수가 나왔을 경우 연산횟수가 많아 질 수 있기 때문에 dp로 이전 값을 가져와서 계산하는 방법을 사용했다.

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

const dp = new Array(num + 1).fill(0);

for (let i = 2; i <= num; i++) {
  dp[i] = dp[i - 1] + 1;

  if (i % 2 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 2] + 1);
  }

  if (i % 3 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  }
}

console.log(dp[num]);

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

5 4
2
8
10
7

7 21

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

const [N, M] = input.shift().split(" ").map(Number);
const arr = input.map(Number);
arr.sort((a, b) => b - a);

const answer = [];

for (let i = 0; i < arr.length; i++) {
  if (i + 1 > N) {
    break;
  }

  // total - 최대 수익, value - 달걀 가격
  answer.push({ total: (i + 1) * arr[i], value: arr[i] });
}

answer.sort((a, b) => b.total - a.total);

console.log(answer[0].value, answer[0].total);

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

3
2 1
8 3
5 7

15

1 2(1번소) 3(1번소 검사완료) 4 5(3번소) 6 7 8 9 10 11 12(3번소 검사완료) 13(2번소) 14 15(2번소 검사완료)
위와 같이 진행될 때 소는 먼저온 순서로 들어가는 형식이다. 그렇기때문에 소의 도착시간 순서로 정렬한 뒤 계산한다.
배열 순회할 때 마다 time에 start + end를 더해준다.
이때, 현재 time > start이면 time에 end 만 더해주고, time <= start 일 경우 start - time + end로 계산한다.
start - time을 하는 이유는 이전에 지나간 시간은 start에서 제거를 해야하기 때문이다.

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

const arr = input.map((el) => el.split(" ").map(Number));
arr.sort((a, b) => a[0] - b[0]);

let time = 0;

arr.forEach((value) => {
  const [start, end] = value;
  if (time > start) {
    time += end;
  } else {
    time += start - time + end;
  }
});

console.log(time);