끄적끄적 코딩
728x90

1. 문제 설명

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

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

2. 제한 조건

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

3. 해결 방법

알고리즘: 구현 (Implementation)

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

4. 시간 복잡도

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

5. 구현 코드

<typescript />
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(); });

검색 태그