728x90
1. 문제 설명
선생님이 초콜릿을 냉장고에 숨겨두었지만, 학생들이 초콜릿을 몰래 먹고 있습니다. 이를 방지하기 위해, 남은 초콜릿의 개수를 특정 규칙에 따라 포스트잇에 기록하려고 합니다. 초콜릿은 **한라봉(H), 감귤(T), 백년초(C), 키위(K), 녹차(G)**의 5가지 종류로 구성되어 있으며, 남은 초콜릿의 총합과 종류별 남은 개수를 다음 규칙에 따라 기록합니다:
- 첫 번째 줄:
- 남은 초콜릿의 총 개수를 기록합니다.
- 이전 총합의 일의 자리 값을 진법으로 사용하여 숫자를 변환합니다.
- 일의 자리가 0 또는 1이면 10진법을 사용합니다.
- 변환된 숫자 뒤에 7H를 붙입니다.
- 두 번째 줄:
- 남아있는 초콜릿 개수가 많은 순서대로 초콜릿 종류를 공백 없이 나열합니다.
- 남은 개수가 같다면, 알파벳 순서로 정렬합니다.
- 남은 초콜릿이 없으면 "NULL"을 출력합니다.
2. 제한 조건
- 초콜릿 종류별 초기 개수 H,T,C,K,G: 1 이상 1,000,000 이하
- 초콜릿을 먹는 횟수 M: 1 이상 1,000 이하
- 각 종류별 먹은 초콜릿 개수는 초기 개수 이하로 제한됩니다.
3. 해결 방법
알고리즘: 구현 (Implementation)
- 문제의 핵심
- 초콜릿 종류별 남은 개수를 단계별로 계산하여 기록합니다.
- 출력 형식은 남은 총합의 진법 변환 및 정렬된 종류별 초콜릿 알파벳으로 구성됩니다.
- 구현 방식
- 초콜릿 종류별 남은 개수를 객체로 관리합니다.
- 각 초콜릿 종류의 남은 개수를 차감하며 총합을 계산합니다.
- 총합의 일의 자리 값으로 진법을 결정합니다:
- 일의 자리가 0 또는 1이면 10진법 사용.
- 남은 초콜릿 개수를 정렬합니다:
- 남은 개수 기준 내림차순, 개수가 같다면 알파벳 순.
- 남은 초콜릿이 없으면 "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();
});
'알고리즘' 카테고리의 다른 글
[Javascript] 백준 1912번 연속합 (0) | 2025.01.07 |
---|---|
[Javascript] 백준 25957번 단어 우월 효과 (0) | 2025.01.06 |
[Javascript] 프로그래머스 - 예산 (0) | 2025.01.04 |
[Javascript] 프로그래머스 - 영어 끝말잇기 (0) | 2025.01.04 |
[Javascript] 프로그래머스 - 점프와 순간 이동 (0) | 2025.01.04 |