Homile

문제

봄이 오고 있다. 해는 높이 떠서 환하게 빛나고 있다. 사람들은 햇볕을 가리기 위해 블라인드를 내린다.

상근이는 이웃들이 무엇을 하는지를 염탐하고, 이것에 대해서 뒷담화를 하는 주부이다. 올해는 건너편 아파트에 사는 사람들이 블라인드를 얼마나 내리는지를 조사하려고 한다. 

모든 창문은 4×4 그리드로 나타낼 수 있고, *를 이용해서 블라인드를 나타낸다. 상근이가 볼 수 있는 창문은 다음 5가지 상태 중 하나이다.

건너편 아파트의 한 층에는 N개의 창문이 있고, 총 M층 건물이다. 현재 건너편 아파트의 창문 상태가 주어졌을 때, 위의 5가지 상태가 각각 몇 번 나오는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 M과 N이 공백으로 구분해서 주어진다. (1 ≤ M, N ≤ 100)

다음 줄에는 현재 건너편 아파트의 상태가 주어진다. 모든 창문은 문제 설명에 나온 것 처럼 4*4 그리드로 주어진다. 또, 창문과 창문은 '#'를 이용해서 구분한다. 예제 입력 형식을 참고하면 좋다. 아파트의 정보는 5M+1줄, 각 줄은 5N+1개 글자로 이루어져 있다.

출력

출력은 총 5개 숫자이다. 문제 설명에 나온 순서대로 각 블라인드 타입이 몇 개 있는지를 출력한다. 숫자를 모두 합하면 M*N이 되어야 한다.

문제

소희는 공개키와 개인키 한 쌍으로 보안을 유지하는 것이 매우 불편하다고 생각했다. 그래서 소희는 공개키만을 이용하는 암호화 체계를 개발했다. 이를 "철벽 보안 알고리즘"이라고 부르기로 했다. 알고리즘은 다음과 같다.

한 단어는 1~10개의 대문자(A-Z)들로 이루어진 문자열이다. 한 문장은 공백으로 구분된 단어들로 이루어졌다.

제 1 공개키는 최대 한 번만 사용된 단어들로 되어있다.

제 2 공개키는 제 1 공개키의 단어들을 재배치하여 만들어진다.

평문(암호화 되지 않은 문장)은 제 1 공개키와 같이 여러 단어들로 되어있지만, 제 1 공개키와 다르게 각 단어들은 중복이 가능하다.

암호문(암호화 된 문장)은 평문을 제 2 공개키를 만든 규칙의 반대로 재배치하여 만들어진다.

주어진 2개의 공개키와 암호문으로 평문을 복구하라.

입력

입력의 첫 줄에는 테스트 케이스의 수를 의미하는 하나의 정수가 입력된다. 정수는 100을 넘지 않는다.

각 테스트케이스마다 아래 항목들을 한 줄씩 입력받는다.

• 한 문장의 단어 수 n (1 ≤ n ≤ 1 000)
• 제 1 공개키
• 제 2 공개키
• 암호문

모든 단어들은 최소 1개, 최대 10개의 대문자들로 이루어져있다.

출력

각 케이스마다

• 암호문을 해독한 평문

을 한 줄에 줄력한다.

2
4
A B C D
D A B C
C B A P
3
SECURITY THROUGH OBSCURITY
OBSCURITY THROUGH SECURITY
TOMORROW ATTACK WE

B A P C
WE ATTACK TOMORROW

문제풀이(1)

1. 1공개키의 위치에 맞는 2공개키의 인덱스 번호를 구한다.
    ㄴ 1공개키: A B C D, 2공개키: D A B C 일 때, 2공개키의 인덱스는 4 1 2 3 이다.

2. 암호문을 2공개키로 구한 인덱스번호에 맞춰서 해독한다.
    ㄴ 암호문: C B A P, 2공개키의 인덱스: 4 1 2 3 일 때, 해독하면 B A P C 가 된다.

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

const T = Number(input.shift());

const answer = [];

const checkIndex = (publicKey1, publicKey2) => {
  return publicKey2.map((targetKey) => publicKey1.indexOf(targetKey));
};

for (let i = 0; i < T; i++) {
  const wordCount = Number(input.shift());
  const publicKey1 = input.shift().split(" ");
  const publicKey2 = input.shift().split(" ");
  const ciphertext = input.shift().split(" ");

  const matchIndex = checkIndex(publicKey1, publicKey2);

  const arr = Array.from({ length: wordCount }).fill("");

  matchIndex.forEach((el, idx) => {
    arr[el] = ciphertext[idx];
  });

  answer.push(arr.join(" "));
}

console.log(answer.join("\n"));

문제

N개의 자연수가 좌우로 배열되어 있다. 여러분은 이 중 K개를 골라야 한다. 고를 때는 K개 모두를 한번에 골라야 한다.

여러분이 고른 수 각각에 대해서 그 수의 점수를 계산할 것이다. 점수는 자신의 수에서 자신의 왼쪽에 있는 수 중 선택된 수의 개수를 뺀 값이다. 이렇게 고른 수 각각에 그 점수를 계산한 후 전체점수는 계산된 점수들의 합이다. 여러분은 전체점수가 최대가 되도록 K개의 수를 골라야 한다.

예를 들어서, N = 5개의 자연수가 순서대로 2 3 1 2 1 로 주어지고, K = 3이라고 하자. 만약 첫 번째 2와 두 개의 1을 골랐다면, 각 수의 점수를 계산해서 나열하면 2 0 −1과 같다. 따라서 전체 점수는 1이다. 만약 첫 번째 2와 3, 그리고 두 번째 2를 고르고, 각 수의 점수를 계산해서 나열하면, 2 2 0과 같다. 따라서 전체점수는 4이다. 이 예에서 전체점수의 최댓값은 4이다.

N개의 자연수 배열과 양의 정수 K가 주어질 때, 전체점수의 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 N과 K가 공백 하나를 사이로 두고 주어진다. 두 번째 줄에 N개의 자연수가 공백 하나를 사이에 두고 주어진다.

출력

첫 번째 줄에 주어진 N개의 수 중 K개의 수를 고를 때, 전체점수의 최댓값을 출력한다.

제한

• 1 ≤ N ≤ 5 000
• 1 ≤ K ≤ N
• 주어지는 자연수는 1 이상 100 000 이하

서브태스크

6 2
4 1 5 2 6 3

10

문제풀이(1)

문제

정수 M개가 주어졌을 때, 모든 두 수의 쌍 중에서 가장 큰 최대공약수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 N (1 < N < 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 양의 정수 M (1 < M < 100)개가 주어진다. 모든 수는 -231보다 크거나 같고, 231 -1보다 작거나 같다. 

출력

각 테스트 케이스마다, 입력으로 주어진 수의 모든 두 수의 쌍의 최대공약수 중 가장 큰 값을 출력한다.

3
10 20 30 40
7 5 12
125 15 25

20
1
25

문제풀이(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());

const result = [];

const getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

for (let i = 0; i < N; i++) {
  const numbers = input[i].split(" ").map(BigInt);
  let max = 0;
  for (let j = 0; j < numbers.length; j++) {
    for (let k = j + 1; k < numbers.length; k++) {
      let gcd = getGCD(numbers[j], numbers[k]);
      if (gcd > max) max = gcd;
    }
  }
  result.push(max.toString());
}

console.log(result.join("\n"));

문제

올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다. (연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)

예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.

배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 배열의 원소가 한 줄에 하나씩 주어진다. 원소는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 배열에 중복되는 수는 없다.

출력

첫째 줄에 입력으로 주어진 배열이 올바른 배열이 되게 하기 위해서 추가되어야할 원소의 최소 개수를 출력한다.

6
5
7
9
8492
8493
192398

2

문제풀이(1)

배열안에 5개 연속으로 나올 수 있는 경우 0, 없을 경우 추가해야할 원소의 최소 개수를 구하는 문제이다.
주어진 배열에 값들을 오름차순으로 정렬한다.
연속적으로 숫자를 추가한 뒤 필요하지 않은 값들을 제거하여 크기를 비교한다.

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

const getMaxContinuousNum = (numbers) => {
  let max = 0;

  for (let i = 0; i < numbers.length; i++) {
    const set = new Set([numbers[i] + 1, numbers[i] + 2, numbers[i] + 3, numbers[i] + 4]);
    let cnt = 0;

    for (let j = 0; j < numbers.length; j++) {
      if (set.has(numbers[j])) {
        cnt++;
      }
    }

    max = Math.max(max, cnt);
  }

  return max;
};

const [N, ...numbers] = input.map(Number);
numbers.sort((a, b) => a - b);

console.log(4 - getMaxContinuousNum(numbers));

문제

정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.

출력

첫째 줄에 정수 N의 제곱근을 출력한다.