끄적끄적 코딩
728x90

문제 설명

선생님이 초콜릿을 냉장고에 숨겨두었지만, 학생들이 초콜릿을 몰래 먹고 있습니다. 이를 방지하기 위해, 남은 초콜릿의 개수를 특정 규칙에 따라 포스트잇에 기록하려고 합니다. 초콜릿은 **한라봉(H), 감귤(T), 백년초(C), 키위(K), 녹차(G)**의 5가지 종류로 구성되어 있으며, 남은 초콜릿의 총합과 종류별 남은 개수를 다음 규칙에 따라 기록합니다:

  1. 첫 번째 줄:
    • 남은 초콜릿의 총 개수를 기록합니다.
    • 이전 총합의 일의 자리 값을 진법으로 사용하여 숫자를 변환합니다.
    • 일의 자리가 0 또는 1이면 10진법을 사용합니다.
    • 변환된 숫자 뒤에 7H를 붙입니다.
  2. 두 번째 줄:
    • 남아있는 초콜릿 개수가 많은 순서대로 초콜릿 종류를 공백 없이 나열합니다.
    • 남은 개수가 같다면, 알파벳 순서로 정렬합니다.
    • 남은 초콜릿이 없으면 "NULL"을 출력합니다.

제한 조건

  • 초콜릿 종류별 초기 개수 H,T,C,K,G: 1 이상 1,000,000 이하
  • 초콜릿을 먹는 횟수 M: 1 이상 1,000 이하
  • 각 종류별 먹은 초콜릿 개수는 초기 개수 이하로 제한됩니다.

해결 방법

알고리즘: 구현 (Implementation)

  • 문제의 핵심
    • 초콜릿 종류별 남은 개수를 단계별로 계산하여 기록합니다.
    • 출력 형식은 남은 총합의 진법 변환 및 정렬된 종류별 초콜릿 알파벳으로 구성됩니다.
  • 구현 방식
    1. 초콜릿 종류별 남은 개수를 객체로 관리합니다.
    2. 각 초콜릿 종류의 남은 개수를 차감하며 총합을 계산합니다.
    3. 총합의 일의 자리 값으로 진법을 결정합니다:
      • 일의 자리가 0 또는 1이면 10진법 사용.
    4. 남은 초콜릿 개수를 정렬합니다:
      • 남은 개수 기준 내림차순, 개수가 같다면 알파벳 순.
    5. 남은 초콜릿이 없으면 "NULL"을 출력합니다.

시간 복잡도

  • 정렬 연산: 초콜릿 종류는 항상 5개로 고정, 정렬은 O(1)
  • 총합 및 정렬 반복: 먹는 횟수 M만큼 반복, O(M)
  • 총 시간 복잡도: O(M)

구현 코드

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input: string[] = [];

readline
  .on("line", function (line: string) {
    input.push(line);
  })
  .on("close", function () {
    interface Chocolate {
      num: number;
      index: number;
      text: string;
    }

    const order: number[] = [2, 4, 0, 3, 1];
    const labels: string[] = ["H", "T", "C", "K", "G"];
    const list: Chocolate[] = input[0].split(" ").map((num, index) => {
      return {
        num: parseInt(num),
        index: order[index],
        text: labels[index],
      };
    });

    const eatList: number[][] = input.slice(2).map((line) => line.split(" ").map(Number));

    let sum: number = list.reduce((a, c) => a + c.num, 0);
    let base: number = sum % 10 <= 1 ? 10 : sum % 10;

    for (const eat of eatList) {
      sum = list.reduce((a, c, i) => {
        c.num -= eat[i];
        return a + c.num;
      }, 0);

      const orderStr: string = list
        .filter((item) => item.num > 0)
        .sort((a, b) => (b.num === a.num ? a.index - b.index : b.num - a.num))
        .map((item) => item.text)
        .join("");

      console.log(`${sum.toString(base)}7H`);
      console.log(orderStr || "NULL");

      base = sum % 10 <= 1 ? 10 : sum % 10;
    }

    process.exit();
  });

검색 태그