Homile

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

3
ABAB
AABB
ABBA

2

3
AAA
AA
AB

1

문제풀이(1)

꾸벅꾸벅 졸다가 모든 글자의 A와 B가 바뀌었다면 그냥 ctr+z를 눌르면 될 것 같다는 생각이 들었지만 예시이기 때문에 넘어가기로 했다.
단어 위로 아치형 곡선을 그어 같은 글자끼리 짝을 짓고 선이 겹치지 않는 다는 것이 어떤 말인지 잘 감이 잡히지 않아서 직접 그려보았다.

ABAB -> 곡선을 그었을때 첫번째 B와 두번쨰 A의 곡선이 겹치기 떄문에 좋은 단어가 아니다.
AABB -> 곡선을 그었을때 겹치지 않기 떄문에 좋은 단어이다.
ABBA -> 곡선을 그었을때 겹치지 않기 때문에 좋은 단어이다.
규칙성을 보았을 때, 올바른 괄호와 같은 형식으로 풀면될 것 같다.

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

let answer = 0;

arr.forEach((word) => {
  if (word.length % 2 === 0) {
    const stack = [];

    for (let i = 0; i < word.length; i++) {
      if (stack.length === 0) {
        stack.push(word[i]);
        continue;
      }

      if (stack.at(-1) === word[i]) {
        stack.pop();
      } else {
        stack.push(word[i]);
      }
    }

    if (stack.length === 0) {
      answer++;
    }
  }
});

console.log(answer);

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

5
1
2
1
2
1

1

6
1
2
1
2
1
2

1

문제풀이(1)

가지고 있는 정수 중에 가장 많이 가지고 있는 정수를 고르되, 가장 많이 가지고 있는 정수가 여러개라면 낮은 수를 출력한다.
Map을 사용하여 카운팅하면서 동시에 가장 큰수와, 가장 큰수의 개수를 비교하여 변경한다.
Number 범위를 초과하기 때문에 BigInt를 사용해야하며 출력시 toString을 사용해야한다.

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

const map = new Map();
let maxNum;
let maxCount = 0;

for (let i = 0; i < N; i++) {
  const num = arr[i];

  map.has(num) ? map.set(num, map.get(num) + 1) : map.set(num, 1);

  if (num === maxNum) {
    maxCount++;
    continue;
  }

  if (map.get(num) > maxCount) {
    maxNum = num;
    maxCount = map.get(num);
  } else if (map.get(num) === maxCount && num < maxNum) {
    maxNum = num;
    maxCount = map.get(num);
  }
}

console.log(maxNum.toString());

문제풀이(2) - 리팩토링

1. 코드의 가독성 향상 - 반복적으로 사용되는 값 변수할당, 조건문 간소화

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

const map = new Map();
let maxNum;
let maxCount = 0;

for (let i = 0; i < N; i++) {
  const num = arr[i];
  const currentCount = (map.get(num) || 0) + 1;

  map.set(num, currentCount);

  if (num === maxNum) {
    maxCount++;
  } else if (currentCount > maxCount || (currentCount === maxCount && num < maxNum)) {
    maxNum = num;
    maxCount = currentCount;
  }
}

console.log(maxNum.toString());

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

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

2
4

문제풀이(1)

상근이가 가장 적은 종류의 비행기를 타고 이동하는 값을 찾는 문제이다. (다른 국가를 거쳐가도 된다.)
첫번째는 테스트 케이스의 수, 두번째부터는 국가의 수와 비행기의 종류가 입력된다.
모든 곳이 연결된 비행 스케줄은 항상 연결 그래프를 이루기 때문에 (나라수 - 1)이 된다.

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

const answer = [];

for (let i = 0; i < T; i++) {
  const [country, airplane] = arr[0].split(" ").map(Number);
  arr.shift();
  for (let j = 0; j < airplane; j++) {
    arr.shift();
  }
  answer.push(country - 1);
}

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

문제풀이(2)

문제풀이(1)와 같이 풀 경우 shift를 많이 사용하여 배열의 이동이 잦아지기 때문에 비효율적이다.
1. shift메소드를 사용하지 않고, 인덱스를 직접관리해서 효율적으로 변경한다.
시간복잡도 - O(n * m) -> O(n)
메모리 - 31944kb -> 20168ms
실행시간 - 4272kb -> 160ms

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

let index = 0;
const T = Number(input[index++]);

let result = "";

for (let i = 0; i < T; i++) {
  const [country, airplane] = input[index++].split(" ").map(Number);
  index += airplane;
  result += country - 1 + "\n";
}

console.log(result.trim());

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

adaabc aababbc

2

hello xello

1

문제풀이(1)

문자열 A를 B에 겹쳤을 때 다른곳의 최소값을 구하면된다.
A문자열의 길이 - B의 문자열의 길이만큼 반복순회하고,
B의 문자열을 한칸씩 뒤로 미루면서 다른곳을 count하여 가장 작은 값을 찾아낸다. -> 슬라이딩 윈도우 기법

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

let min = Infinity;

// A와 B의 차이만큼 반복한다.
for (let i = 0; i <= B.length - A.length; i++) {
  let diff = 0;
  // 한칸씩 뒤로 미루면서 가장 차이가 적은 것을 골라낸다.
  for (let j = 0; j < A.length; j++) {
    if (A[j] !== B[i + j]) {
      diff++;
    }
  }
  min = Math.min(min, diff);
}

console.log(min);

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

16 1 2

1

16 8 9

4

1000 20 31

4

문제풀이(1)

N명의 참가자수 중에서 김지민과 임한수가 무조건 이겨서 둘이 대결하는 라운드를 찾는 문제이다.
이진탐색 알고리즘을 사용하여 풀수 있다.
김지민과 임한수가 무조건 이겨서 올라가고 2명식 경기를 치루기 때문에 각자의 번호 / 2를 해서 반복해서 올라가면서 만나기 전까지를 카운트하면된다.
이문제와 비슷한 문제는 프로그래머스에서 푼기억이 있어서 쉽게 풀 수 있었다.

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

let count = 0;

while (Kim !== Lim) {
  Kim = Math.ceil(Kim / 2);
  Lim = Math.ceil(Lim / 2);
  count++;
}

console.log(count);

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

4 2
12 3
15 4

12

10 3
20 8
40 7
60 4

36

문제풀이(1)

첫번째줄에 주어지는 N, M의 관계 - N은 끊어진 기타줄의 개수이고, M은 기타줄을 구매할 수 있는 브랜드의 개수이다.
두번째줄 이후로는 패키지의 가격, 1개의 가격이 적혀있다. 이때, 1개의 가격이 패키지의 가격보다 비쌀 수 있다.
최소한의 금액으로 N개의 기타줄을 사는 가격을 구하는 문제이다.
1. 패키지의 최소 금액과 1개의 최소 금액을 구한다.
2-1. 6개를 낱개로 사는 것이 패키지를 구매하는 것보다 싸다면 모두 낱개로 구매한다.
2-2. 6개를 낱개로 사는 것이 패키지를 구매하는 것보다 비싸다면 N/6의 몫만큼 패키지로 구매하고, 나머지를 패키지로 구매하는 것과 낱개로 구매하는 것중에 싼것을 찾는다.
3. 2-1, 2-2에서 나온 값들의 합을 출력한다.

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 brand = input.map((line) => line.split(" ").map(Number));

const minPackage = brand.reduce((min, curr) => (curr[0] < min ? curr[0] : min), brand[0][0]);
const minPiece = brand.reduce((min, curr) => (curr[1] < min ? curr[1] : min), brand[0][1]);
const pacakgeCount = Math.floor(N / 6);
const pieceCount = N % 6;

let answer = 0;

// 낱개로 사는 것 보다 패키지로 구매하는게 효율이 좋을 경우
if (minPackage / 6 < minPiece) {
  // 패키지 만큼 구매
  answer += pacakgeCount * minPackage;
  // 패키지 만큼 구매하고 남은 낱개를 구매할 때 더 가격이 낮은쪽을 구매
  answer += pieceCount * minPiece < minPackage ? pieceCount * minPiece : minPackage;
} else {
  // 낱개로 사는 것 보다 패키지로 구매하는게 효율이 좋지 않을 경우
  answer += N * minPiece;
}

console.log(answer);

문제풀이(2) - 리팩토링

1. 가독성을 위해 변수명 수정
2. 불필요한 조건문 제거

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 brand = input.map((line) => line.split(" ").map(Number));

const minPackage = brand.reduce((min, curr) => (curr[0] < min ? curr[0] : min), brand[0][0]);
const minPiece = brand.reduce((min, curr) => (curr[1] < min ? curr[1] : min), brand[0][1]);
const pacakgeCount = Math.floor(N / 6);
const pieceCount = N % 6;

let totalCost = pacakgeCount * minPackage + Math.min(pieceCount * minPiece, minPackage);

if (minPackage / 6 >= minPiece) {
  totalCost = N * minPiece;
}

console.log(totalCost);