Homile

문제

한슬이는 5와 8이 행운의 수라고 생각한다. 그래서 한슬이는 각 자리가 5와 8로만 이뤄져 있는 수를 행운의 수라고 한다.

정수 수열 A, B, C가 주어졌을 때 세 수열에서 각각 하나의 정수를 골라서 만들 수 있는 서로 다른 행운의 수의 개수를 구해보자.

예를 들어 A = [1, 10, 100], B = [3, 53], C = [4, 54]라고 한다면, 행운의 수를 만드는 방법은 8 = 1 + 3 + 4, 58 = 1 + 3 + 54, 58 = 1 + 53 + 4와 같이 총 3가지가 있다. 58은 2가지 방법으로 만들 수 있으니, 서로 다른 행운의 수의 개수는 8과 58, 총 2개이다.

입력

첫째 줄에 테스트 케이스의 수가 주어진다.

각 테스트 케이스의 첫째 줄에 A의 크기 N이 주어지고, 둘째 줄에 수열 A의 원소가 주어진다. 수열 A의 원소는 공백으로 구분되어 있다.

다음 셋째 줄에는 B의 크기 M, 넷째 줄에는 수열 B의 원소, 다섯째 줄에는 C의 크기 K, 여섯째 줄에는 C의 원소가 주어지며, 수열 A의 정보와 같은 형식으로 되어 있다.

수열의 크기는 50을 넘지 않는 양의 정수이고, 수열의 원소는 30,000보다 작거나 같은 양의 정수이다.

출력

각각의 테스트 케이스마다 입력으로 주어진 수열을 이용해 만들 수 있는 서로 다른 행운의 수의 개수를 한 줄에 하나씩 출력한다.

2
6
100 1 10 100 1 1
7
3 53 53 53 53 53 53
6
4 54 4 54 4 54
1
47
1
500
1
33

2
0

문제풀이(1)

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

for (let i = 0; i < T; i++) {
  const testCaseArr = input.splice(0, 6);
  const A = testCaseArr[1].split(" ").map(Number);
  const B = testCaseArr[3].split(" ").map(Number);
  const C = testCaseArr[5].split(" ").map(Number);

  const luckySet = new Set();

  for (const a of A) {
    for (const b of B) {
      for (const c of C) {
        const sum = a + b + c;
        if (isLuckyNumber(sum)) {
          luckySet.add(sum);
        }
      }
    }
  }
  console.log(luckySet.size);
}

function isLuckyNumber(num) {
  const forbiddenDigits = ["0", "1", "2", "3", "4", "6", "7", "9"];
  const digits = num.toString().split("");
  return !digits.some((digit) => forbiddenDigits.includes(digit));
}

문제

사이클 단어는 어떤 단어를 원형 모양으로 차례대로 쓴 것이다. 따라서, 어떤 단어를 이렇게 쓴 후에 임의의 단어를 고른다. 그 후에 시계방향으로 차례대로 읽으면 그 것이 단어가 된다. 만약에 단어 A와 단어 B가 있을 때, 단어 B를 원형으로 써서, 단어 A와 같이 읽을 수 있으면, 두 단어는 같은 단어이다. 따라서, picture와 turepic은 같은 단어다.

N개의 단어가 주어졌을 때, 서로 다른 단어가 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 단어가 한 줄에 하나씩 주어진다. 단어는 영어 소문자로만 이루어져 있다. N은 50보다 작거나 같은 자연수이며, 단어의 길이는 최대 50이다.

출력

첫째 줄에 서로 다른 단어가 몇 개인지 출력한다.

문제

크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다.

여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구하자. 즉, max1 ≤ i ≤  j ≤ N (X[i]+...+X[j])를 구하자.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000)

그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

출력

각 테스트케이스 별로 maximum subarray의 합을 줄로 구분하여 출력한다.

2
5
1 2 3 4 5
5
2 1 -2 3 -5

15
4

문제풀이(1)

DP문제
1. 현재값, 현재값 + 이전값 중 큰수를 쌓아준다.
2. 테스트 케이스별로 최대값을 구한다.

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 = [];

for (let i = 0; i < T; i++) {
  const N = Number(input.shift());
  const nums = input.shift().split(" ").map(Number);
  for (let i = 1; i < nums.length; i++) {
    nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
  }

  answer.push(Math.max(...nums));
}

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

문제

N(3≤N≤999, N은 홀수)명의 학생들이 원 모양으로 둘러앉아 있다. 각 학생들은 모두 몇 개의 사탕(≤100,000)을 가지고 있는데 그 개수는 사람마다 다를 수 있고, 사탕을 아예 가지고 있지 않을 수도 있다. 물론 사탕의 개수는 음이 아닌 정수이다.

편의상 학생들에게 번호를 매기는데, 반시계 방향으로 1번 학생, 2번 학생, …, N번 학생으로 번호를 매겼다. 1번 학생 오른쪽엔 2번 학생, 2번 학생 오른쪽엔 3번 학생이 앉아 있는 것이고, 마지막 N번 학생 오른쪽엔 1번 학생이 앉아 있게 된다.

우리는 인접한 두 학생이 가지고 있는 사탕의 수의 합을 안다. 즉 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생이 가지고 있는 사탕의 수의 합, …, N-1번 학생과 N번 학생이 가지고 있는 사탕의 수의 합, 마지막으로 N번 학생과 1번 학생의 가지고 있는 사탕의 수의 합을 안다. 이때, 각 학생이 가지고 있는 사탕의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(3 ≤ N ≤ 999, N은 홀수)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 1번 학생과 2번 학생이 가지고 있는 사탕의 수의 합, 2번 학생과 3번 학생이 가지고 있는 사탕의 수의 합, …, N-1번 학생과 N번 학생이 가지고 있는 사탕의 수의 합, 마지막으로 N번 학생과 1번 학생의 가지고 있는 사탕의 수의 합이 순서대로 주어진다.

출력

첫째 줄부터 N개의 줄에 걸쳐 1번 학생이 가지고 있는 사탕의 수, 2번 학생이 가지고 있는 사탕의 수, …, N번 학생이 가지고 있는 사탕의 수를 순서대로 출력한다. 출력하는 수는 음이 아닌 정수들이어야 하며, 항상 답이 존재하는 경우만이 입력으로 주어진다고 가정해도 좋다.

3
5
7
6

2
3
4

문제풀이(1)

문제

숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10)

이미지 I는 크기가 R × C인 2차원 픽셀이다. (3 ≤ R ≤ 40, 3 ≤ C ≤ 40) 각 픽셀은 어두운 정도 V를 나타낸다. (0 ≤ V ≤ 255)

중앙 필터는 이미지에 있는 노이즈를 제거하는 필터이다. 필터의 크기는 3 × 3이고, 이미지의 중앙값을 찾으면서 잡음을 제거한다.

예를 들어, 아래와 같은 6 × 5 이미지가 있다.

필터링된 이미지의 크기는 4 × 3이고, 아래와 같다.

가장 왼쪽 윗 행에 필터를 두고, 오른쪽으로 움직이면서 중앙값을 찾는다. 한 행을 모두 이동했으면, 다음 행으로 이동해 다시 중앙값을 찾는다. 아래와 같은 순서를 가진다.

위의 그림에서 각각의 중앙값은 36, 36, 21이 된다. 이 값은 필터링된 이미지 J의 첫 행과 같다. 

이미지 I가 주어졌을 때, 필터링 된 이미지 J를 구하고, 값이 T보다 크거나 같은 픽셀의 수를 구하는 프로그램을 작성하시오.

예를 들어, T = 40일 때, 위의 예에서 정답은 7이다. 

입력

첫째 줄에 이미지의 크기 R과 C가 주어진다. 그 다음 R개의 각 줄에는 C개의 픽셀 값이 주어진다. 마지막 줄에는 T값이 주어진다.

출력

첫째 줄에 필터링 된 이미지 J의 각 픽셀 값 중에서 T보다 크거나 같은 것의 개수를 출력한다.