silver

백준 PS 난이도 실버 문제 모음

[백준 문제풀이] 8979번 올림픽


8979번 올림픽 (Silver 3)

문제

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

올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다.

금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 많은 나라 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 얻었고, 2번 국가와 3번 국가가 모두 은메달 1개를 얻었으며, 4번 국가는 메달을 얻지 못하였다면, 1번 국가가 1등, 2번 국가와 3번 국가가 공동 2등, 4번 국가가 4등이 된다. 이 경우 3등은 없다.

각 국가의 금, 은, 동메달 정보를 입력받아서, 어느 국가가 몇 등을 했는지 알려주는 프로그램을 작성하시오.

입력

입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다.

출력

출력은 단 한 줄이며, 입력받은 국가 K의 등수를 하나의 정수로 출력한다. 등수는 반드시 문제에서 정의된 방식을 따라야 한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// 입력 값 처리 부분
const fs = require("fs");
const [numbers, ...medals] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .split("\n")
  .map((line) => line.split(" ").map((el) => el * 1));
const [N, K] = numbers;

solveProblem();

// 문제 해결 방식
// 1. 주어진 K 값으로 탐색하여 target을 구한다.
// 2. target과 타국들과의 메달 비교를 통해 rank를 도출.
function solveProblem() {
  const target = getTarget(K, medals);
  const rank = getRank(target, medals);

  console.log(rank);
}

// target 국가를 구하는 함수
// 주어진 K를 전체 국가의 ID과 비교하여 찾는다.
// @return {Array}: target 국가 정보
function getTarget(K, medals) {
  let result;
  for (let i = 0; i < N; i++) {
    if (medals[i][0] === K) result = medals[i];
  }

  return result;
}

// rank를 구하는 함수
// 금메달 비교 후 target 국가보다 많으면 rank + 1
// 금메달이 같으면, 은메달 비교 후 target 국가보다 많으면 rank + 1
// 은메달이 같으면, 동메달 비교 후 target 국가보다 많으면 rank + 1
// @return {number}: 최종 rank를 반환
function getRank(target, medals) {
  let result = 1;

  // 전체 국가와 비교
  for (let i = 0; i < N; i++) {
    // 본인 국가는 지나가기
    if (medals[i][0] === target[0]) continue;

    if (medals[i][1] >= target[1]) {
      // 금메달 비교
      if (medals[i][1] > target[1]) {
        result++;
      } else if (medals[i][2] >= target[2]) {
        // 은메달 비교
        if (medals[i][2] > target[2]) {
          result++;
        } else if (medals[i][3] >= target[3]) {
          // 동메달 비교
          if (medals[i][3] > target[3]) {
            result++;
          }
        }
      }
    }
  }

  return result;
}

[백준 문제풀이] 1063번 킹


1063번 킹 (Silver 3)

문제

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

8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 행을 상징한다. 열은 가장 왼쪽 열이 A이고, 가장 오른쪽 열이 H까지 이고, 행은 가장 아래가 1이고 가장 위가 8이다. 예를 들어, 왼쪽 아래 코너는 A1이고, 그 오른쪽 칸은 B1이다.

킹은 다음과 같이 움직일 수 있다.

R : 한 칸 오른쪽으로 L : 한 칸 왼쪽으로 B : 한 칸 아래로 T : 한 칸 위로 RT : 오른쪽 위 대각선으로 LT : 왼쪽 위 대각선으로 RB : 오른쪽 아래 대각선으로 LB : 왼쪽 아래 대각선으로 체스판에는 돌이 하나 있는데, 돌과 같은 곳으로 이동할 때는, 돌을 킹이 움직인 방향과 같은 방향으로 한 칸 이동시킨다. 아래 그림을 참고하자.

입력으로 킹이 어떻게 움직여야 하는지 주어진다. 입력으로 주어진 대로 움직여서 킹이나 돌이 체스판 밖으로 나갈 경우에는 그 이동은 건너 뛰고 다음 이동을 한다.

킹과 돌의 마지막 위치를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 킹의 위치, 돌의 위치, 움직이는 횟수 N이 주어진다. 둘째 줄부터 N개의 줄에는 킹이 어떻게 움직여야 하는지 주어진다. N은 50보다 작거나 같은 자연수이고, 움직이는 정보는 위에 쓰여 있는 8가지 중 하나이다.

출력

첫째 줄에 킹의 마지막 위치, 둘째 줄에 돌의 마지막 위치를 출력한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
const fs = require("fs");
let [chessPieces, ...commands] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

chessPieces = chessPieces.split(" ");
const N = chessPieces.pop();

solveProblem();

function solveProblem() {
  // 이동을 숫자의 증감으로 표현할 수 있도록
  // 열을 숫자로 변환함.
  chessPieces = positionToAscii(chessPieces);

  // 명령 배열을 돌며 명령 수행
  commands.forEach((command) => {
    chessPieces = handleCommand(chessPieces, command);
  });

  // 출력을 위해 다시 체스 포지션 문자열로 변경
  chessPieces = asciiToPosition(chessPieces);

  // 결과 출력
  console.log(chessPieces.join("\n"));
}

// 명령 수행
// @chessPieces {Array}: king, stone의 위치 정보를 담은 이차원 배열
// @command {String}: 명령 문자열
// @return {Array}: king, stone의 위치 정보를 담고 있는 이차원 배열
function handleCommand(chessPieces, command) {
  let [king, stone] = chessPieces;

  // king 이동.
  king = moveChessPiece(king, command);
  if (king[0] === stone[0] && king[1] === stone[1]) {
    // king과 store의 위치가 같으면,
    // stone도 이동시킴.
    stone = moveChessPiece(stone, command);
  }

  // 두 말의 위치가 보드 내에 있다면,
  // 변경된 위치 정보 반환
  if (checkPosition(...king) && checkPosition(...stone)) return [king, stone];

  // 두 말의 위치가 보드 밖에 있다면,
  // 변경전 위치 정보 반환
  return chessPieces;
}

// 체스말 이동 함수
// @chessPiece {Array} : 이동할 체스말 위치 정보
// @command {String}: 명령 문자열
function moveChessPiece(chessPiece, command) {
  let [movedColumn, movedRow] = chessPiece;

  switch (command[0]) {
    case "R":
      movedColumn++;
      break;
    case "L":
      movedColumn--;
      break;
    case "T":
      movedRow++;
      break;
    case "B":
      movedRow--;
      break;
  }

  if (command[1]) {
    switch (command[1]) {
      case "T":
        movedRow++;
        break;
      case "B":
        movedRow--;
        break;
    }
  }

  return [movedColumn, movedRow];
}

// 위치 확인 함수
// 체스말의 위치가 보드 내에 있는지 확인
// @column, row {String}: 체스말 열, 행 정보
// @return {Boolean}
function checkPosition(column, row) {
  if (column >= 65 && column <= 72 && row >= 1 && row <= 8) return true;

  return false;
}

// 체스판 위치 => 아스키코드 변환 함수
// @return {Array} : 아스키코드로 변환된 king, stone의 위치 정보 이차원 배열
function positionToAscii(chessPieces) {
  chessPieces = chessPieces.map((chessPiece) => {
    chessPiece = chessPiece.split("");
    chessPiece[0] = chessPiece[0].charCodeAt();
    chessPiece[1] = chessPiece[1] * 1;

    return chessPiece;
  });

  return chessPieces;
}

// 아스키코드 => 체스판 위치 변환 함수
// @return {Array} : 문자열로 변환된 king, stone의 위치 정보 배열
function asciiToPosition(chessPieces) {
  chessPieces = chessPieces.map((chessPiece) => {
    chessPiece[0] = String.fromCharCode(chessPiece[0]);
    chessPiece[1] = chessPiece[1] * 1;

    return chessPiece.join("");
  });

  return chessPieces;
}

[백준 문제풀이] 10799번 쇠막대기


10799번 쇠막대기 (Bronze 1)

문제

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

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다.

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

풀이

=> )를 pop의 기준으로 사용하는 스택을 작성해서 풀이했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

const stack = [];
let cutNum = 1;
let answer = 0;

for (let i = 0; i < input.length; i++) {
  switch (input[i]) {
    case ")":
      if (input[i - 1] === "(") {
        stack.pop();
        answer += stack.length;
      } else if (stack.length) {
        stack.pop();
        answer++;
      }
      break;
    default:
      stack.push(input[i]);
  }
}

console.log(answer);

[백준 문제풀이] 17413번 단어 뒤집기 2


17413번 단어 뒤집기 2 (Silver 3)

문제

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

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.

먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.

알파벳 소문자(‘a’-‘z’), 숫자(‘0’-‘9’), 공백(‘ ‘), 특수 문자(‘<’, ‘>’)로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ‘<’와 ‘>’가 문자열에 있는 경우 번갈아가면서 등장하며, ‘<’이 먼저 등장한다. 또, 두 문자의 개수는 같다. 태그는 ‘<’로 시작해서 ‘>’로 끝나는 길이가 3 이상인 부분 문자열이고, ‘<’와 ‘>’ 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.

출력

첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.

풀이

switch case로 stack을 만들어서 풀었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();

const stack = [];
let isTag = false;
let answerStr = "";

function reverseStr(str) {
  switch (str) {
    case "<":
      while (stack.length) {
        answerStr += stack.pop();
      }
      answerStr += str;
      isTag = true;
      break;
    case ">":
      answerStr += str;
      isTag = false;
      break;
    case " ":
      if (!isTag) {
        while (stack.length) {
          answerStr += stack.pop();
        }
      }
      answerStr += str;
      break;
    case undefined:
      while (stack.length) {
        answerStr += stack.pop();
      }
      break;
    default:
      if (isTag) {
        answerStr += str;
      } else {
        stack.push(str);
      }
  }
}

for (let i = 0; i <= input.length; i++) {
  reverseStr(input[i]);
}

console.log(answerStr);

[백준 문제풀이] 10866번 덱


10866번 덱 (Silver 4)

문제

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

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 덱에 들어있는 정수의 개수를 출력한다. empty: 덱이 비어있으면 1을, 아니면 0을 출력한다. front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 –1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

N이 10,000 이하라서 배열을 만들고 shift, pop을 사용해서 풀이했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input[0]);
const answerArr = [];
const deque = [];

const workDeque = (lineData) => {
  switch (lineData[0]) {
    case "pop_front":
      answerArr.push(deque.length ? deque.shift() : -1);
      break;
    case "pop_back":
      answerArr.push(deque.length ? deque.pop() : -1);
      break;
    case "size":
      answerArr.push(deque.length);
      break;
    case "empty":
      answerArr.push(deque.length ? 0 : 1);
      break;
    case "front":
      answerArr.push(deque.length ? deque[0] : -1);
      break;
    case "back":
      answerArr.push(deque.length ? deque[deque.length - 1] : -1);
      break;
    case "push_back":
      deque.push(lineData[1]);
      break;
    default:
      deque.unshift(lineData[1]);
      break;
  }
};

for (let i = 1; i <= N; i++) {
  const line = input[i].split(" ");
  workDeque(line);
}

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

[백준 문제풀이] 1874번 스택수열


1874번 스택수열 (Silver 3)

문제

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

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

첫번째 풀이

입력 숫자가 n번째 수보다 크면 같아질 때까지 push하고, 작으면 pop을 하는 방법으로 풀이했다. 방법이 없을때를 고려해서 try, catch를 사용했다.

첫번째 풀이 소스코드 (메모리 초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const n = parseInt(input.shift());
const stack = [];
const answerArr = [];
let isExist = true;

for (let j = 0; j < n; j++) {
  let num = 1;
  while (num <= n) {
    if (num <= parseInt(input[j])) {
      while (num <= parseInt(input[j])) {
        stack.push(num);
        answerArr.push("+");
        num++;
      }
    } else {
      try {
        while (stack[stack.length - 1] !== parseInt(input[j])) {
          stack.pop();
          answerArr.push("-");
        }
        stack.pop();
        answerArr.push("-");
      } catch {
        isExist = false;
      }
    }
  }
}

if (!isExist) {
  console.log("NO");
} else {
  console.log(answerArr.join("\n"));
}

최종 풀이

문제에서 요구하는 로직을 다시 정리해보자면,

  1. 1부터 n까지의 수를 오름차순으로 스택에 넣어야한다.
  2. 그 과정에서 제시되는 숫자 순서대로 스택에서 숫자를 pop 한다.
  3. 이것이 가능하다면 push와 pop의 로그를 출력하고,
  4. 불가능하다면 ‘NO’를 출력해라.

라고 정리할 수 있겠다.

이 알고리즘은

  1. stack에 순서대로 push 하고 pop하는 알고리즘
  2. 해당 숫자열이 스택 수열로 가능한지 확인하는 조건문

두 가지로 나눠볼 수 있겠다.

1. stack에 순서대로 push 하고 pop하는 알고리즘

먼저 오름차순대로 스택에 입력하고, 제시되는 순서대로 pop 하는 알고리즘을 생각해본다면.

  1. 1부터 첫번째 제시된 숫자까지 stack에 push 한다.
  2. 두번째로 제시된 숫자가 첫번째로 제시된 숫자보다 작으면, 두번째로 제시된 숫자까지 pop한다.
  3. 두번째로 제시된 숫자가 첫번째로 제시된 숫자보다 크면, 두번째로 제시된 숫자까지 stack에 push 한다.

위의 과정을 반복하면 된다.

2. 해당 숫자열이 스택 수열로 가능한지 확인하는 조건문

stack에 순서대로 push 하고 pop하는 알고리즘이 진행될 때, 스택 수열로 가능한지에 대한 조건문이 사용되어야한다.

스택 수열이 불가능한 경우를 생각해보면

push 해야할 수가 제시된 숫자보다 더 크고, 제시된 숫자보다 stack에 있는 수가 제시된 수보다 경우이다.

이 경우에는, stack에서 아무리 pop 하더라도 제시된 수를 만들 수 없다.

최종 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const n = parseInt(input.shift());
const stack = [];
const answerArr = [];
let isExist = true; // 가능 / 불가능 확인을 위한 flag
let num = 1; // push 해야할 수

for (let j = 0; j < n; j++) {
  if (num <= parseInt(input[j])) {
    // push 해야 할 수가 제시된 수보다 작으면
    // 제시된 수까지 push 한다.
    while (num <= parseInt(input[j])) {
      stack.push(num);
      answerArr.push("+");
      num++;
    }
  } else if (stack[stack.length - 1] > parseInt(input[j])) {
    // push 해야 할 수가 제시된 수보다 크고,
    // stack에 있는 수가 제시된 수보다 크면
    // 아무리 pop해도 스택 수열을 만들 수 없다.
    isExist = false;
    break;
  }

  // 제시된 수까지 push 되었기 때문에,
  // pop 해주면 된다.
  stack.pop();
  answerArr.push("-");
}

if (!isExist) {
  console.log("NO");
} else {
  console.log(answerArr.join("\n"));
}

[백준 문제풀이] 10845번 큐


10845번 큐 (Silver 4)

문제

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

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 –1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

배열로 Queue를 만들어서 풀이했다.

첫번째 풀이 소스코드 (시간 초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const N = parseInt(input[0]);
const que = [];
const answerArr = [];

function workQue(cmd) {
  switch (cmd) {
    case "pop":
      answerArr.push(que.length ? que.shift() : -1);
      break;
    case "size":
      answerArr.push(que.length);
      break;
    case "empty":
      answerArr.push(que.length ? 0 : 1);
      break;
    case "front":
      answerArr.push(que.length ? que[0] : -1);
      break;
    case "back":
      answerArr.push(que.length ? que[que.length - 1] : -1);
      break;
    default:
      const line = cmd.split(" ");
      que.push(parseInt(line[1]));
  }
}

for (let i = 1; i <= N; i++) {
  workQue(input[i]);
}

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

[백준 문제풀이] 1158번 요세푸스 문제


1158번 요세푸스 문제 (Silver 4)

문제

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

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

풀이

에디터 때와 같이 두 개의 배열을 통해 풀려고 했는데, 하나의 큐를 만들어서 풀 수 있을 것 같았다. N도 5000 이하로 크지 않아서, 시도해보기로 했다.

에디터 문제 보러가기

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");

const N = parseInt(input[0]);
const K = parseInt(input[1]);

let queue = new Array(N);
queue = queue.fill(0).map((el, index) => (el = index + 1));

let count = 0;
const answerArr = [];

// K번째 있는 사람을 죽이는 함수
// length가 K보다 클 때와 작을 때를 나누어 구현했다.
function kill(cnt) {
  while (cnt !== 0) {
    if (queue.length >= cnt) {
      queue.push(...queue.splice(0, cnt));
      answerArr.push(queue.pop());
      cnt = 0;
    } else {
      cnt -= queue.length;
    }
  }
}

while (count < N) {
  kill(K);
  count++;
}

console.log(`<${answerArr.join(", ")}>`);

사족

다른 사람들의 풀이를 확인해보니, shift를 사용해서 한 사람들은 시간이 더 걸렸고, 배열로 큐나 스택을 직접 구현 하지 않고, index로만 값에 접근 하면 더 빠른 코드를 구현할 수 있었다.


[백준 문제풀이] 1406번 에디터


1406번 에디터 (Silver 2)

문제

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

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임 P $ $라는 문자를 커서 왼쪽에 추가함 초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

첫번째 풀이

배열로 만든 뒤 cursor의 index를 사용해서 문제를 풀려고 시도했다.

첫번째 풀이 소스코드 (시간 초과)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let str = input.shift();
str = str.trim().split("");
const N = parseInt(input.shift());
let index = parseInt(str.length > 0 ? str.legnth - 1 : 0);

for (let i = 0; i < N; i++) {
  switch (input[i].trim()) {
    case "L":
      if (index !== 0) {
        index -= 1;
      }
      break;
    case "D":
      if (index !== str.length - 1) {
        index += 1;
      }
      break;
    case "B":
      if (index !== 0) {
        str.splice(index - 1, 1);
      }
      break;
    default:
      const line = input[i].split(" ");
      str.splice(index - 1, 0, line[1]);
  }
}

console.log(str.join(""));

최종 풀이

단순 배열로 풀이하면, 중간에 추가하는 동안의 시간 복잡도가 최대 O(n)으로 시간 초과가 날 수 밖에 없었다.

자료구조로 접근하기로 했다. cursor의 왼쪽과 오른쪽을 배열로 만들어서 오른쪽은 Que, 왼쪽은 Stack의 자료구조로 구현하면 가능할 것이라고 생각했다.

이 경우도 시간 초과가 떠서 찾아보니 pop / push 메서드가 시간복잡도가 O(1)인 것과 달리, shift / unshift 메서드는 배열 맨 앞 요소를 빼야하기 때문에 시간복잡도가 O(n)이어서였다.

이 경우는 두 가지 방법을 생각해볼 수 있었다.

  1. 양쪽 다 스택으로 구현하여 풀이한 뒤, right 배열을 뒤집어서 쓴다.
  2. class를 통해서 유사 배열 객체로 queue를 생성하여서 시간복잡도를 O(1)로 만들어서 푼다.

나는 양쪽 다 스택으로 구현한 뒤 커서 오른쪽의 배열을 뒤집어서 쓰는 방법을 사용했다.

최종 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

let str = input.shift();
const N = parseInt(input.shift());
const cursorLeft = str.trim().split("");
let cursorRight = [];

for (let i = 0; i < N; i++) {
  switch (input[i]) {
    case "L":
      if (cursorLeft.length) {
        cursorRight.push(cursorLeft.pop());
      }
      break;
    case "D":
      if (cursorRight.length) {
        cursorLeft.push(cursorRight.pop());
      }
      break;
    case "B":
      if (cursorLeft.length) {
        cursorLeft.pop();
      }
      break;
    default:
      const line = input[i].split(" ");
      cursorLeft.push(line[1]);
  }
}

cursorRight = cursorRight.reverse();

console.log([...cursorLeft, ...cursorRight].join(""));

[백준 문제풀이] 9012번 괄호


9012번 괄호 (Silver 4)

배운 것

조건문에 사용된 문도 실행된 것으로 처리된다. if문에 stack.pop()을 통해서 값이 남아있는지 확인하려고 했었는데, 이 부분에서 배열의 값이 pop 되는 바람에 계속 에러가 났었다.

문제

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

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

풀이

스택을 사용해서 풀 수 있었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const T = parseInt(input.shift());
const answerArr = [];

for (let i = 0; i < T; i++) {
  const line = input[i];
  const stack = [];
  let answer = "YES";

  for (let j = 0; j < line.length; j++) {
    if (line[j] === "(") {
      stack.push("(");
    } else {
      if (!stack.pop()) {
        answer = "NO";
        break;
      }
    }
  }
  if (stack.length > 0) {
    answer = "NO";
  }

  answerArr.push(answer);
}

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

[백준 문제풀이] 10828번 스택


10828번 스택 (Silver 4)

배운 것

빈 배열에서 pop을 실행하면 에러가 나는 것이 아니라, undefined가 나온다.

&&과   연산자를 활용하면 코드를 간결하게 만들 수 있다. 하지만 많이 사용하면 가독성이 떨어질 수 있다.

문제

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

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 –1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

스택과 큐

스택 : 택배 상하차 (입출구가 동일) 큐 : 한정판 대기열 (입출구가 다름)

스택은 후입선출 자료구조로 LIFO(Last In First Out)로, 큐는 선입선출 자료구조로 FIFO(First In First Out)이라고도 부른다.

풀이

처음에 문제를 보고 멘붕와서 각 함수를 구현해야하나 생각했었는데, 돌아보니 그럴 필요까지는 없고 그냥 조건문을 사용하면 될 것 같았다. 이 경우 if 문을 사용하는 것보다 switch case 조건문을 사용하는 것이 나을 것 같았다.

이번에는 stack과 알고리즘 관련해서 모르는 것이 많아서 구글에서 나온 블로그를 참고해서 풀이했다.

참고 풀이 : https://gurtn.tistory.com/67 (나를 제외한 천재들)

유튜브, 구글, 다른 스택 풀이들을 보니 결국 js에서 1차원 스택은 여러 상황이나 조건에 따라 구현이 다르겠지만, 당장은 배열을 통한 풀이를 생각할 수 있었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = input.shift();
const stack = [];
const answerArr = [];

for (let i = 0; i < N; i++) {
  switch (input[i]) {
    case "pop":
      answerArr.push(stack.length ? stack.pop() : -1);
      break;
    case "size":
      answerArr.push(stack.length);
      break;
    case "empty":
      answerArr.push(stack.length ? 0 : 1);
      break;
    case "top":
      answerArr.push(stack.length ? stack[stack.length - 1] : -1);
      break;
    default:
      stack.push(input[i].split(" ")[1]);
  }
}

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

[백준 문제풀이] 18870번 좌표 압축


18870번 좌표 압축 (Silver 2)

문제

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

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

출력

첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.

좌표 압축이란?

좌표 압축이란, 정확한 값이 필요 없고 값의 대소관계만이 필요할 때, 모든 수를 0이상 N 미만의 수로 바꾸는 것을 말한다.

첫번째 풀이

N이 1,000,000 이하의 수 인데다가, X는 2 * 10^2만큼의 범위를 가져서 단순 정렬로는 풀지 못할 것이라고 생각했다.

일단 메모리 제한이 512MB인데다가 N이 X보다는 훨씬 적은 범위라서 N만큼의 배열을 만든 뒤, set 객체를 사용해서 함수 중복을 제거한 뒤에 index 값으로 원배열 값을 바꿔주는 것을 생각했다.

첫번째 풀이 소스코드 (시간 초과 - set 객체로 변환 후, index 값으로 변환)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input.shift());
let numbers = input.toString().trim().split(" ");
const set = new Set(numbers);
const setArr = [...set];
setArr.sort();

const indexArr = new Array(setArr.length);

for (let i = 0; i < N; i++) {
  const index = indexArr.indexOf(numbers[i]);
  numbers[i] = index;
}

console.log(numbers.join(" "));

두번째 풀이

시간 초과가 나올만한 부분이 탐색 부분인 것 같아서 indexOf의 시간복잡도를 찾아보니 O(n)으로 나왔다. n이 최대 1,000,000에 O(n)으로 최대 1,000,000번 탐색해야하니, 시간 초과가 나올 수 밖에 없었다.

이때 사용을 고려 해볼 수 있는 방법으로 객체에 담아서 해시테이블로 사용하는 것과 이진탐색을 사용하는 것이었다. 객체에 담는 forEach의 시간복잡도 또한 O(n)이라서, O(logn)의 시간복잡도를 가지는 이진탐색으로 실행하기로 했다.

두번째 풀이 소스코드 (시간 초과 - )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input[0]);
let numbers = input[1]
  .toString()
  .split(" ")
  .map((el) => parseInt(el));
const set = new Set(numbers);
let indexArr = [...set];
indexArr.sort((a, b) => a - b);

for (let i = 0; i < N; i++) {
  let low = 0;
  let high = N - 1;
  let mid = Math.floor(high + low / 2);
  while (numbers[i] !== indexArr[mid]) {
    if (numbers[i] < indexArr[mid]) {
      high = mid - 1;
      mid = Math.floor(high + low / 2);
    } else {
      low = mid + 1;
      mid = Math.floor(high + low / 2);
    }
  }
  numbers[i] = mid;
}

console.log(numbers.join(" "));

세번째 풀이

이진 탐색도 결국 최대 1,000,000번 해야했기 때문에, 시간 초과가 나올 수 밖에 없었다.

결국 hash table을 사용하는 방식으로 풀어야 했다. 생각해보니까 처음에 forEach로 hash table을 만들더라도, 마지막 for문에서 찾을 때 시간복잡도가 O(1)인 것이라서 훨-씬 빨랐다.

최종 풀이 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input[0]);
let numbers = input[1]
  .toString()
  .split(" ")
  .map((el) => parseInt(el));
const set = new Set(numbers);
let indexArr = [...set];
indexArr.sort((a, b) => a - b);
const indexObj = {};

indexArr.forEach((el, index) => (indexObj[el] = index));

for (let i = 0; i < N; i++) {
  numbers[i] = indexObj[numbers[i]];
}

console.log(numbers.join(" "));

[백준 문제풀이] 1181번 단어 정렬


1181번 단어 정렬 (Silver 5)

문제

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

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

  1. 길이가 짧은 것부터
  2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

풀이

Set 객체로 만들어서 반복을 지우고, sort를 두 번 사용해서 풀 수 있었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = input.shift();

let strArr = new Set(input);
strArr = [...strArr];
strArr.sort();

strArr.sort((a, b) => a.length - b.length);

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

구현할 때 왜 단어순 정렬부터 했을까? (2022.05.04)

문제를 보고 바로 생각해볼 수 있는 것은, 단어 순으로 정렬한 뒤, 길이순으로 정렬하는 것이다.

하지만 조금만 더 생각해보면, 그렇게 정렬하게될 경우 단어순으로 정렬하게되며 길이순 정렬이 모두 꼬인다는 것을 생각해볼 수 있다.


[백준 문제풀이] 10814번 나이순 정렬


10814번 나이순 정렬 (Silver 5)

문제

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

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

풀이

가입순으로 이미 정렬되어있기 때문에, 나이 순으로만 정렬할 수 있도록 sort() 메서드를 사용했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = input.shift();
input = input.map((el) => el.split(" "));

input.sort((a, b) => parseInt(a[0]) - parseInt(b[0]));

input = input.map((el) => el.join(" "));

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

[백준 문제풀이] 좌표 정렬하기 1, 2


11650번, 11651번 좌표 정렬하기 (Silver 5)

두 문제가 작은 차이만 있고, 풀이는 같아서 하나의 게시글에서 다루려고 한다.

11650번 문제

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

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

11651번 문제

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

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력 (동일)

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력 (동일)

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

풀이

sort()로 쉽게 풀 수 있었다.

11650번 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input.shift());
input = input.map((el) => el.split(" "));

input.sort((a, b) => {
  if (parseInt(a[0]) === parseInt(b[0])) {
    return parseInt(a[1]) - parseInt(b[1]);
  } else {
    return parseInt(a[0]) - parseInt(b[0]);
  }
});

input = input.map((el) => el.join(" "));

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

11651번 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input.shift());
input = input.map((el) => el.split(" "));

input.sort((a, b) => {
  if (parseInt(a[1]) === parseInt(b[1])) {
    return parseInt(a[0]) - parseInt(b[0]);
  } else {
    return parseInt(a[1]) - parseInt(b[1]);
  }
});

input = input.map((el) => el.join(" "));

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

[백준 문제풀이] 10989번 수 정렬하기 3


10989번 수 정렬하기 3 (Silver 5)

문제

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

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

시간 제한 5초, 메모리 제한 8MB

접근

힌트가 카운팅 정렬이었어서, 카운팅 정렬에 대해 찾아보았다.

계수 정렬 (Counting sort)

Counting Sort는 O(n)의 시간 복잡도를 가지는 정렬 알고리즘이다. 일반적으로는 평균 시간 복잡도가 O(nlogn)인 Quick Sort 알고리즘이 더 빠르지만 수의 등장 횟수를 누적합으로 바꿔주는 Counting Sort의 경우 수의 범위 특정하게 정해진 경우 range를 구해서 빠르게 정렬할 수 있다. 하지만 대부분의 상황에서 엄청난 메모리 낭비가 될 수 있다.

일단 설명만 보고 스스로 구현을 먼저 해보고, 막히면 찾아보기로 했다.

풀이

범위에 맞는 countArr를 만들어서 풀려고 했는데, 바로 메모리 초과가 나왔다.

찾아보니, node.js는 메모리 초과가 나와서, 추후 제한 완화 예정이라고 해서 파이썬으로 찾아서 문제를 풀었다. 설명되어있는 counting sort를 사용해보고 싶었는데, 생각과는 달리 더 빠른 방법이 있었다.

python으로 풀때도 input으로 받으면 메모리 초과가 나온다고 해서, sys.stdin.readline()을 사용해서 풀었다. 나중에 node.js 메모리 제한이 풀리면 다시 풀어보고 싶다.

파이썬에서는 반복문에 변수가 사용되지 않을 경우, _를 사용한다는 것도 인상깊었다.

그리고 FE 개발자도 파이썬으로 코딩 테스트를 준비하는 이유도 느껴볼 수 있었다…☆

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

N = int(sys.stdin.readline())
num_list = [0] * 10001

for _ in range(N) :
    num = int(sys.stdin.readline())
    num_list[num] += 1

for i in range(10001) :
    countNum = num_list[i]
    for _ in range(countNum) :
        print(i)

[백준 문제풀이] 2751번 수 정렬하기 2


2751번 수 정렬하기 2 (Silver 5)

문제

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

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

첫번째 풀이

sort 메서드를 사용해 간단하게 풀 수 있었다. 새롭게 알게된 사실은 sort 메서드의 시간 복잡도가 O(n log(n)) 이라는 것이었다.

첫번째 풀이 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((el) => parseInt(el));

const N = input.shift();

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

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

사족

지금 생각해보면 sort 메서드를 쓰라고 했던 건 아닌 것 같다. 22년 3월 게시글 중에 다른 정렬 알고리즘들을 구현해두었다.


[백준 문제풀이] 1018번 체스판 다시 칠하기


1018번 체스판 다시 칠하기 (Silver 5)

문제

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

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

풀이

체스판을 먼저 만든 다음, 옳은 체스판과 비교해서 브루트 포스로 카운트 한 뒤 가장 작은 수를 찾아서 풀었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const N = input.shift();
const lines = ["WBWBWBWB", "BWBWBWBW"];
let min = 64;

for (let a = 0; a <= input.length - 8; a++) {
  for (let b = 0; b <= input[a].length - 8; b++) {
    let count = 0;
    for (let k = 0; k < 8; k++) {
      for (let m = 0; m < 8; m++) {
        if (k % 2 === 0) {
          if (input[a + k][b + m] === lines[0][m]) {
            count++;
          }
        } else {
          if (input[a + k][b + m] === lines[1][m]) {
            count++;
          }
        }
      }
    }
    if (count > 32) {
      if (min > 64 - count) min = 64 - count;
    } else {
      if (min > count) min = count;
    }
  }
}

console.log(min);

[백준 문제풀이] 1436번 영화감독 숌


1436번 영화감독 숌 (Silver 5)

문제

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

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, …. 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

입력

첫째 줄에 숫자 N이 주어진다. N은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력한다.

첫번째 풀이

N이 10000까지 되어서 하나씩 수를 증가하면서 푸는 방식은 섹시하지 못할 것 같지만, 다른 로직이 떠오르지 않아서 일단 수행해보았다.

맞았지만, 시간이 544ms로 뭔가 맘에 들지 않았다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
const fs = require("fs");
const input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());
let num = 665;
let count = 0;

while (count !== input) {
  num++;
  if (String(num).includes("666")) {
    count++;
  }
}

console.log(num);

사족

조합을 사용해서 자릿수별 666이 포함되는 범위를 찾는 수식을 세웠다. 자릿수 m이 4 이상일 때, (m-3)(m-3)(m-2)*9/2의 범위에 속하게 되는데, 이 범위를 사용해서 m번째 수의 최소 최댓값을 구하면 코드의 효율을 높일 수 있음을 확인했다.


[백준 문제풀이] 11729번 하노이 탑 이동 순서


11729번 하노이 탑 이동 순서 (Silver 1)

문제

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

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

배운 것

재귀 알고리즘은 선언형 프로그래밍이다.

명령형 프로그래밍은 알고리즘을 명시하고 목표는 명시하지 않는데 반해, 선언형 프로그래밍은 목표를 명시하고 알고리즘을 명시하지 않는 것이다.

즉, 알고리즘에 대해 명시 하는 것이 아니라 목표에 대해 명시하고 알고리즘은 컴퓨터가 해결할 수 있도록 하는 것이 선언형 프로그래밍이다.

목표를 정하고, 종료 조건을 정하고 재귀시켜야한다.

즉, 이 문제에서는 ‘A에서 B로 옮겨라’라는 명령을 추후 일어날 상황까지 고려해서 에러 없는 논리으로 구현하면 되는 것이다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const fs = require("fs");
const input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());

const answer = [];
let count = 0;

function movePlate(from, to, other, num) {
  if (num === 0) {
    return;
  } else {
    movePlate(from, other, to, num - 1);
    answer.push(`${from} ${to}`);
    count++;
    movePlate(other, to, from, num - 1);
  }
}

movePlate(1, 3, 2, input);

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

[백준 문제풀이] 2447번 별 찍기


2447번 별 찍기 (Silver 1)

문제

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

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, …)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

배운 것

재귀 함수라는 개념 자체가 조금 어려워서 구글 서치를 하고, 문서나 영상들을 찾아봤다. 재귀함수도 결국은 수학적 사고로 추론된 규칙을 기반으로 수행되어야 하는 것이라는걸 이해할 수 있었다.

풀이

별찍기의 공백은 n * n으로 만들어질 때, 좌표가 n % 3 === 1인 지점부터 n / 3까지의 공백이다.

3이 아닌 더 큰 수에서는 결국 3으로 나눠준 몫이 이러한 부분을 가지게 된다. 예를 들어서 Math.floor(4 / 3) = Math.floor(3 / 3)이 된다. 이러한 방식을 사용하면, 3^n인 별을 찍을 수 있다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const fs = require("fs");
const input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());
const answer = [];

for (let i = 0; i < input; i++) {
  for (let j = 0; j < input; j++) {
    makeStar(i, j, input);
  }
  answer.push("\n");
}

function makeStar(x, y, num) {
  if (x % 3 === 1 && y % 3 === 1) {
    answer.push(" ");
  } else {
    if (num === 1) {
      answer.push("*");
    } else {
      makeStar(Math.floor(x / 3), Math.floor(y / 3), num / 3);
    }
  }
}

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

[백준 문제풀이] 1002번 터렛


1002번 터렛 (Silver 4)

문제

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

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 –1을 출력한다.

풀이

각 터렛의 위치가 [같음, 다름] 각각의 경우에서 원이 [내접할 때, 외접할 때, 겹칠 때, 반지름이 같을 때]로 나눠서 쉽게 풀 수 있었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const T = parseInt(input[0]);
const answerArr = [];

function checkCount(numArr) {
  const xFir = numArr[0];
  const yFir = numArr[1];
  const rFir = numArr[2];
  const xSec = numArr[3];
  const ySec = numArr[4];
  const rSec = numArr[5];
  const max = Math.max(rFir, rSec);
  const min = Math.min(rFir, rSec);

  const distance = Math.sqrt(
    Math.pow(xFir - xSec, 2) + Math.pow(yFir - ySec, 2)
  );
  if (xFir === xSec && yFir === ySec) {
    if (rFir === rSec) {
      answerArr.push(-1);
      return;
    } else {
      answerArr.push(0);
      return;
    }
  } else {
    if (distance === max) {
      answerArr.push(2);
      return;
    } else if (distance < max) {
      if (distance + min === max) {
        answerArr.push(1);
        return;
      } else if (distance + min < max) {
        answerArr.push(0);
        return;
      } else {
        answerArr.push(2);
        return;
      }
    } else {
      if (distance === max + min) {
        answerArr.push(1);
        return;
      } else if (distance > max + min) {
        answerArr.push(0);
        return;
      } else {
        answerArr.push(2);
        return;
      }
    }
  }
}

for (let i = 1; i <= T; i++) {
  const numbers = input[i].split(" ").map((num) => parseInt(num));
  checkCount(numbers);
}

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

[백준 문제풀이] 9020번 골드바흐의 추측


9020번 골드바흐의 추측 (Silver 1)

문제

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

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

풀이

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const T = parseInt(input[0]);
const answerArr = [];

for (let i = 1; i <= T; i++) {
  const number = parseInt(input[i]);
  let a = number / 2;
  let b = number - a;

  while (true) {
    let isPrime = true;
    if (a % 2 === 0 || b % 2 === 0) {
      if (!(a === 2 && b === 2)) {
        isPrime = false;
      }
    } else {
      for (let m = 3; m <= Math.sqrt(a); m += 2) {
        if (a % m === 0) {
          isPrime = false;
          break;
        }
      }
      if (isPrime) {
        for (let n = 3; n <= Math.sqrt(b); n += 2) {
          if (b % n === 0) {
            isPrime = false;
            break;
          }
        }
      }
    }
    if (isPrime) {
      answerArr.push(`${a} ${b}`);
      break;
    } else {
      a -= 1;
      b += 1;
    }
  }
}

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

사족 (2022.04.26)

이 당시에는 소수를 구하는 방식으로 풀었는데, 지금 돌아보면 에라토스테네스의 체로 접근하는 것이 더 나은 풀이 같다.


[백준 문제풀이] 4948번 베르트랑 공준


4948번 베르트랑 공준 (Silver 2)

문제

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

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

풀이

반복문과 제곱근 나누기 방식의 에라토노스체로 접근했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const fs = require("fs");

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el * 1);

const max = Math.max(...input);
let screen = Array.from({ length: max * 2 + 1 }, () => true);
screen[0] = false;
screen[1] = false;

for (let i = 2; i <= max * 2; i++) {
  if (screen[i]) {
    for (let j = 2; i * j <= max * 2; j++) {
      screen[i * j] = false;
    }
  }
}

let answer = Array.from({ length: input.length - 1 }, () => 0);
for (let i = 0; i < input.length - 1; i++) {
  for (let j = input[i] + 1; j <= input[i] * 2; j++) {
    if (screen[j]) answer[i] += 1;
  }
}

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

[백준 문제풀이] 1929번 소수 구하기


1929번 소수 구하기 (Silver 3)

문제

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

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

시간 제한 : 2초, 메모리 제한 : 256mb

첫 번째 풀이

이번이야말로 에라토스테네스의 체를 사용해야하나 싶었는데, 1,000,000까지 배수의 배열을 만드는 것이 비효율적일 것 같았다. 해서 제곱근까지의 곱을 비교하는 로직을 사용했다.

수가 커서 이전에 사용했던 직접 나누어서 계산하는 로직을 사용하면, 시간 초과가 생길 것 같았다.

직접 나누는 로직의 시간 복잡도는 O(N)이고, 제곱근까지의 수를 나누어서 계산하는 것은 O(√ N)로, 앞의 방법보다 빠르다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const fs = require("fs");
const [M, N] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map((el) => el * 1);

let answer = "";
let screen = Array.from({ length: N + 1 }, () => true);
screen[0] = false;
screen[1] = false;

for (let i = 2; i <= Math.floor(Math.sqrt(N)); i++) {
  if (screen[i]) {
    for (let j = 2; i * j <= N; j++) {
      screen[i * j] = false;
    }
  }
}

for (let i = M; i <= N; i++) {
  if (screen[i]) answer += i + "\n";
}

console.log(answer);

[백준 문제풀이] 11653번 소인수분해


11653번 소인수분해 (Silver 5)

문제

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

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

제한시간 : 1초

첫 번째 풀이

N이 10,000,000이하라서, 전부 일일이 나눠보는 것은 문제가 있다고 생각했다. 소인수분해라는 것은 결국 소수로 나눠지는 것이기 때문에, N까지의 소수를 먼저 구한 뒤 하나씩 나눠보는 방식이 맞다고 생각했다.

아니었다.

두 번째 풀이

작은 수부터 하나씩 나눠보면, 자연스럽게 소인수분해가 된다는 것을 알았다. 다만 나눠지지 않을때는 수를 하나씩 올리면서 실행해보았다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const fs = require("fs");

let input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());
const primes = [];

let divider = 2;
while (input >= divider) {
  if (input % divider === 0) {
    input = input / divider;
    primes.push(divider);
  } else {
    divider++;
  }
}

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

[백준 문제풀이] 2581번 소수


2581번 소수 (Silver 5)

문제

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

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

제한시간 : 1초

풀이

M과 N이 10,000 이하의 자연수라서, 에라토스테네스의 체를 사용해야하나 생각이 들었다. 문제는 메모리가 128mb 라는 것이었다.

그냥 나누기로 했더니 풀렸다. 자꾸 오류가 났었는데, 배열을 Boolean 값으로 검증하는 방식보다 배열의 길이가 0인지 검증하는 쪽이 더 정확하다는 것을 알게되었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const a = parseInt(input[0]);
const b = parseInt(input[1]);
const primeNumbers = [];
let sum = 0;

for (let i = a; i <= b; i++) {
  if (i === 2) {
    primeNumbers.push(i);
    sum += i;
  } else if (i !== 1) {
    let multiple = false;
    for (let l = 2; l < i; l++) {
      if (i % l === 0) {
        multiple = true;
      }
    }
    if (!multiple) {
      primeNumbers.push(i);
      sum += i;
    }
  }
}

if (!primeNumbers.length) {
  console.log(-1);
} else {
  const min = Math.min(...primeNumbers);
  console.log(sum);
  console.log(min);
}

[백준 문제풀이] 1978번 소수 찾기


1978번 소수 찾기 (Silver 4)

문제

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

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데, 수는 1000 이하의 자연수이다.

풀이 : 에라토스테네스의 체

소수를 구하는 공식이 있을 것 같아서 서치해보았고, 에라토스테네스의 체라는 것을 알게 되었다. 에라토스테네스의 체는 1이 아닌 수의 배수들을 제외한 값들을 소수로 판단하여 계산하는 것으로, 모든 수를 그 이하의 다른 수로 나누는 것보다 효율적이라고 한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input[0]);
const numbers = input[1].trim().split(" ");
const nonMultiples = [];

numbers.map((number) => {
  let multiple = false;

  if (parseInt(number) === 1) {
    multiple = true;
  }

  for (let l = 2; l < parseInt(number); l++) {
    if (parseInt(number) % l === 0) {
      multiple = true;
    }
  }

  if (parseInt(number) === 2) {
    nonMultiples.push(number);
  } else if (!multiple) {
    nonMultiples.push(number);
  }
});

if (numbers === []) {
  console.log(0);
} else {
  console.log(nonMultiples.length);
}

2021.11.08. 백준 문제풀이


1316번 그룹 단어 체커 (Silver 5)

문제

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

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

풀이

먼저 set을 이용해서, 중복되는 문자가 없을 때의 경우를 제외해주고 반복문을 통해 확인하기로 정했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().split("\n");

const n = parseInt(input[0]);
let answer = 0;

for (let i = 1; i <= n; i++) {
  const letters = input[i].split("");
  const newLetter = [];
  const set = new Set(letters);
  if (letters.length === set.size) {
    answer += 1;
  } else {
    let isGroupWord = true;
    for (let j = 0; j < letters.length; j++) {
      if (newLetter.indexOf(letters[j]) === -1) {
        newLetter.push(letters[j]);
      } else {
        if (newLetter.indexOf(letters[j]) !== newLetter.length - 1) {
          isGroupWord = false;
          break;
        }
      }
    }
    if (isGroupWord) {
      answer += 1;
    }
  }
}

console.log(answer);

반복문에서는 isGroudWord라는 Boolean 값을 통해서, GroupWord의 상태가 유지되는지 확인하였고, 다른 배열에 문자들을 추가하여서 그 배열의 중복 값이 마지막에 위치해있는지를 통해서 연속적으로 문자가 배치되어있는지 확인했다.


2021.11.07. 백준 문제풀이


2941번 크로아티아 알파벳 (Silver 5)

느낀 점

처음에는 알파벳 문자열 순서에 맞춘 조건문을 사용하려다가 너무 섹시하지 않아서 다른 방법을 고안했다. 정규표현식과 replace로 문자열 대치를 하면 쉽게 풀 수 있을 것 같아서 찾아봤는데 비슷하게 푼 사례가 있어서 참고해서 간단하게 풀 수 있었다.

에러

trim()을 사용안해서 오류가 생겼었다.

문제

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

소스코드

1
2
3
4
5
6
7
8
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim();

const regex = /c\=|c\-|dz\=|d\-|lj|nj|s\=|z\=/g;
const output = input.replace(regex, "Q");

console.log(output.length);

Check out other tags: