Homile

문제

79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 먼저 온다.

문제는 정수 M, N(1 ≤ M ≤ N ≤ 99)이 주어지면 M 이상 N 이하의 정수를 숫자 하나씩 읽었을 때를 기준으로 사전순으로 정렬하여 출력하는 것이다.

입력

첫째 줄에 M과 N이 주어진다.

출력

M 이상 N 이하의 정수를 문제 조건에 맞게 정렬하여 한 줄에 10개씩 출력한다.

문제

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:

• t(0)=1
• t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0)

이 정의에 따르면,

• t(1)=t(0)*t(0)=1
• t(2)=t(0)*t(1)+t(1)*t(0)=2
• t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5
• ...

주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n (0 ≤ n ≤ 35)이 주어진다.

출력

첫째 줄에 t(n)을 출력한다.

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

3 5
2 5 4
1 2 3 4 5

0

문제풀이(1)

A 집합에는 속하지만 B 집합에는 속하지 않는 A 집합의 값을 찾는 문제이다.
두가지 풀이방법을 생각할 수 있다.
1. set 객체를 활용해서 집합 B를 set 객체에 할당한뒤 집합 A를 순회하며 집합 B에 존재 유무를 판단하면 된다.
2. 2진 탐색을 활용하여 집합 B에 집합 A의 값이 존재 유무를 판단하면 된다.
2진 탐색은 O(log N)의 시간복잡도를 갖지만 
set 객체를 활용한 풀이은 O(N)의 시간복잡도를 가지게 되어 이럴경우는 2진탐색보다 set 객체를 활용한 풀이가 더 좋다.

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

input.shift();

const arrA = input[0].split(" ").map(Number);
const arrB = new Set(input[1].split(" ").map(Number));

const answer = [];

arrA.forEach((num) => {
  if (!arrB.has(num)) {
    answer.push(num);
  }
});

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

console.log(answer.length === 0 ? 0 : `${answer.length}\n${answer.join(" ")}`);

문제풀이(2) - 2진탐색 풀이

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

input.shift();

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

const answer = [];

const binarySearch = (arr, target) => {
  let low = 0;
  let high = arr.length - 1;
  let result = false;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (arr[mid] < target) {
      low = mid + 1;
    } else if (arr[mid] > target) {
      high = mid - 1;
    } else {
      result = true;
      break;
    }
  }
  return result;
};

arrA.forEach((num) => {
  if (!binarySearch(arrB, num)) {
    answer.push(num);
  }
});

console.log(answer.length === 0 ? 0 : `${answer.length}\n${answer.join(" ")}`);

문제

KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.

예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다.

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

입력

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.

두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.

출력

재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 231-1보다 작거나 같다.

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

6 9
-||--||--
--||--||-
|--||--||
||--||--|
-||--||--
--||--||-

31

문제풀이(1)

나무판자 -, |가 있을 때 ----|로 있다면 - 나무판자 1개 | 나무판자 1개가 된다.
--|--| 가 있다면 - 나무판자 2개 | 나무판자 2개가 된다.
간단하게 푼다면 for문을 사용해서 가로 나무판자와 세로 나무판자를 구하는 로직을 작성하면된다.
효율성이 있게 알고리즘을 작성한다면 DFS로 방문한 곳과 방문하지 않은 곳을 판단하여 나무판자의 개수를 구할 수 있다.

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);

let answer = 0;

// 가로 탐색
for (let i = 0; i < N; i++) {
  let flag = true;
  for (let j = 0; j < M; j++) {
    const woodenPlank = input[i][j];
    if (flag === true && woodenPlank === "-") {
      answer++;
      flag = false;
    } else if (woodenPlank === "|") {
      flag = true;
    }
  }
}

// 세로 탐색
for (let i = 0; i < M; i++) {
  let flag = true;
  for (let j = 0; j < N; j++) {
    const woodenPlank = input[j][i];
    if (flag === true && woodenPlank === "|") {
      answer++;
      flag = false;
    } else if (woodenPlank === "-") {
      flag = true;
    }
  }
}

console.log(answer);

총총이는 친구 곰곰이의 소개로 제2회 곰곰컵에 출연할 기회를 얻었다!

총총이는 자신의 묘기인 무지개 댄스를 선보여, 여러분의 환심을 사려 한다. 이 댄스는 중독성이 강하기 때문에, 한번 보게 된 사람은 모두 따라 하게 돼버린다.

사람들이 만난 기록이 시간 순서대로 N개 주어진다. (총총이는 토끼이지만 이 문제에서는 편의상 사람이라고 가정한다.)

무지개 댄스를 추지 않고 있던 사람이 무지개 댄스를 추고 있던 사람을 만나게 된다면, 만난 시점 이후로 무지개 댄스를 추게 된다.

기록이 시작되기 이전 무지개 댄스를 추고 있는 사람은 총총이 뿐이라고 할 때, 마지막 기록 이후 무지개 댄스를 추는 사람이 몇 명인지 구해보자!

입력

첫번째 줄에는 사람들이 만난 기록의 수  (1≤N≤1 000)이 주어진다.

두번째 줄부터 N개의 줄에 걸쳐 사람들이 만난 기록이 주어진다. i + 1번째 줄에는 i번째로 만난 사람들의 이름 A_i와 B_i가 공백을 사이에 두고 주어진다. A_i와 B_i는 숫자와 영문 대소문자로 이루어진 최대 길이 20의 문자열이며, 서로 같지 않다.

총총이의 이름은 ChongChong으로 주어지며, 기록에서 1회 이상 주어진다.

동명이인은 없으며, 사람의 이름은 대소문자를 구분한다. (ChongChong과 chongchong은 다른 이름이다.)

출력

마지막 기록 이후 무지개 댄스를 추는 사람의 수를 출력하라.