누적 계산사전 고치기열쇠 순서로P0178

항목별 예산 장부

한 달 가계부에 항목별 예산 한도가 있고, 쓴 돈이 한 줄씩 적힌다. 첫 줄에 예산을 정한 항목 수 c가, 다음 c줄에 "항목 한도"가 주어진다. 이어서 기록 수 n이, 다음 n줄에 기록 "항목 금액"이 주어진다. 금액이 양수면 쓴 돈이고, 음수면 돌려받은 돈(환불)이며, 0일 수도 있다. 예산을 정하지 않은 항목도 기록에 나올 수 있고, 그런 항목의 한도는 0이다. 항목마다 쓴 돈은 0에서 시작해 그 항목의 금액을 차례로 더한 값이다. 기록마다 한 줄에 "전체누적 항목누적"을 출력하라. 전체누적은 지금까지 모든 기록의 금액 합이고, 항목누적은 이 기록을 더한 뒤 그 항목의 쓴 돈이다. 이 기록 직전에는 그 항목의 쓴 돈이 한도 이하였는데 이 기록을 더한 뒤 한도보다 커졌다면, 그 줄 끝에 빈칸 하나와 "over"를 붙인다. 이미 한도보다 큰 상태에서 더 쓴 기록에는 over를 붙이지 않는다. 환불로 한도 이하로 돌아온 뒤 다시 한도를 넘으면 그 기록에 over를 다시 붙인다. 모든 기록 다음에, 예산을 정한 항목과 기록에 나온 항목을 모두 이름의 사전 순으로 한 줄씩 "항목 쓴돈 한도 남은돈"으로 출력하라. 남은돈은 한도에서 쓴 돈을 뺀 값이며 음수일 수 있다. 사전 순은 앞 글자부터 비교해 알파벳이 앞선 쪽이 앞서고, 한쪽이 다른 쪽의 앞부분이면 짧은 쪽이 앞선다.

입력: 1 ≤ c ≤ 100, 1 ≤ n ≤ 3000, 0 ≤ 한도 ≤ 10^12, −10^9 ≤ 금액 ≤ 10^9(정수).
항목 이름은 영어 소문자 1 ~ 10글자이고, 예산 줄의 이름은 모두 다르며, 나오는 항목은 모두 합쳐 100개 이하
출력: n줄의 "전체누적 항목누적"(넘어간 순간에는 끝에 " over"), 이어서 항목마다 사전 순으로 "항목 쓴돈 한도 남은돈"

예시 1 · stdin

3
food 50000
rent 300000
book 20000
6
food 30000
rent 300000
food 25000
game 5000
food -10000
food 6000

stdout

30000 30000
330000 300000
355000 55000 over
360000 5000 over
350000 45000
356000 51000 over
book 0 20000 20000
food 51000 50000 -1000
game 5000 0 -5000
rent 300000 300000 0

예시 2 · stdin

1
bus 0
4
bus 0
bus -500
bus 500
bus 1

stdout

0 0
-500 -500
0 0
1 1 over
bus 1 0 -1

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

누적 합 두 가지(전체 하나, 항목마다 사전 하나)를 함께 굴리는 문제예요.
전체누적은 3,000 × 10억 = 3조까지 가서 C int, Java·C# int로는 넘쳐요.
C long long, Java·C# long을 쓰고, Python·JS·TS·크레이콘은 그대로 돼요(3조는 2^53 안이에요).
사전 고치기는 "없으면 0에서 시작"이에요: Python spent.get(name, 0), JS·TS spent.get(name) ?? 0, Java getOrDefault(name, 0L), C# GetValueOrDefault(name, 0), C++ spent[name](없으면 0을 만들어요), 크레이콘은 만약 (!spent.있나(name)) { spent[name] = 0; }을 먼저 해요.
한도 사전은 C++에서 limit[name]으로 읽으면 없는 항목이 사전에 새로 생기니 count(name)으로 먼저 물어요.
C는 사전이 없어서 이름 표를 차례로 찾아요.
마지막 표는 열쇠 순서로 돌아요: Python sorted(spent), JS·TS [...spent.keys()].sort(), Java TreeMap, C# SortedDictionary(StringComparer.Ordinal), C++ std::map(늘 정렬돼 있어요), 크레이콘 열쇠목록을 정렬(), C qsort+strcmp.
함정 하나: JS Map·Python dict·크레이콘 사전은 넣은 차례로 돌아서 정렬을 빼면 예산 줄 순서대로 나와요.
함정 둘: 예산을 정하지 않은 항목을 Python limit[name]으로 읽으면 KeyError, Java long cap = limit.get(name)은 null을 풀다가 NullPointerException이에요.
함정 셋: over는 "넘어 있는 동안"이 아니라 "넘어가는 순간"이라 before <= cap && after > cap이에요.
함정 넷: 전체누적을 int로 두면 21억을 넘는 순간 음수로 돌아요.

Pythonmain.py · 29 줄

import sys lines = sys.stdin.read().split("\n")c = int(lines[0])limit = {}spent = {}for line in lines[1:1 + c]:    name, cap = line.split()    limit[name] = int(cap)    spent[name] = 0n = int(lines[1 + c])total = 0out = []for line in lines[2 + c:2 + c + n]:    name, amount = line.split()    amount = int(amount)    cap = limit.get(name, 0)            # 예산을 정하지 않은 항목은 한도 0    before = spent.get(name, 0)    spent[name] = before + amount    total += amount                     # 전체 누적    row = f"{total} {spent[name]}"    if before <= cap < spent[name]:     # 한도 안에서 밖으로 넘어간 순간만        row += " over"    out.append(row) for name in sorted(spent):              # 열쇠를 사전 순으로    cap = limit.get(name, 0)    out.append(f"{name} {spent[name]} {cap} {cap - spent[name]}")print("\n".join(out))

JavaScriptmain.js · 30 줄

const lines = require("fs").readFileSync(0, "utf8").split("\n");const c = Number(lines[0]);const limit = new Map();const spent = new Map();for (const line of lines.slice(1, 1 + c)) {  const [name, cap] = line.trim().split(" ");  limit.set(name, Number(cap));  spent.set(name, 0);}const n = Number(lines[1 + c]);let total = 0;const out = [];for (const line of lines.slice(2 + c, 2 + c + n)) {  const [name, a] = line.trim().split(" ");  const amount = Number(a);  const cap = limit.get(name) ?? 0; // 예산을 정하지 않은 항목은 한도 0  const before = spent.get(name) ?? 0;  const after = before + amount;  spent.set(name, after);  total += amount;  out.push(`${total} ${after}` + (before <= cap && after > cap ? " over" : ""));} // Map은 넣은 차례를 지키므로 열쇠를 따로 정렬해야 사전 순이 된다for (const name of [...spent.keys()].sort()) {  const cap = limit.get(name) ?? 0;  const s = spent.get(name) ?? 0;  out.push(`${name} ${s} ${cap} ${cap - s}`);}console.log(out.join("\n"));

TypeScriptmain.ts · 31 줄

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const c = Number(lines[0]);const limit = new Map<string, number>();const spent = new Map<string, number>();for (const line of lines.slice(1, 1 + c)) {  const [name, cap] = line.trim().split(" ");  limit.set(name, Number(cap));  spent.set(name, 0);}const n = Number(lines[1 + c]);let total = 0;const out: string[] = [];for (const line of lines.slice(2 + c, 2 + c + n)) {  const [name, a] = line.trim().split(" ");  const amount = Number(a);  const cap = limit.get(name) ?? 0; // 예산을 정하지 않은 항목은 한도 0  const before = spent.get(name) ?? 0;  const after = before + amount;  spent.set(name, after);  total += amount;  out.push(`${total} ${after}` + (before <= cap && after > cap ? " over" : ""));} // Map은 넣은 차례를 지키므로 열쇠를 따로 정렬해야 사전 순이 된다for (const name of [...spent.keys()].sort()) {  const cap = limit.get(name) ?? 0;  const s = spent.get(name) ?? 0;  out.push(`${name} ${s} ${cap} ${cap - s}`);}console.log(out.join("\n"));

JavaMain.java · 37 줄

import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int c = Integer.parseInt(br.readLine().trim());        Map<String, Long> limit = new HashMap<>();        Map<String, Long> spent = new TreeMap<>(); // TreeMap은 열쇠를 사전 순으로 지킨다        for (int i = 0; i < c; i++) {            String[] p = br.readLine().trim().split(" ");            limit.put(p[0], Long.parseLong(p[1]));            spent.put(p[0], 0L);        }        int n = Integer.parseInt(br.readLine().trim());        long total = 0; // 3,000 × 10억 = 3조라 int로는 넘친다        StringBuilder out = new StringBuilder();        for (int i = 0; i < n; i++) {            String[] p = br.readLine().trim().split(" ");            long amount = Long.parseLong(p[1]);            long cap = limit.getOrDefault(p[0], 0L); // 예산을 정하지 않은 항목은 한도 0            long before = spent.getOrDefault(p[0], 0L);            long after = before + amount;            spent.put(p[0], after);            total += amount;            out.append(total).append(' ').append(after);            if (before <= cap && after > cap) out.append(" over");            out.append('\n');        }        for (Map.Entry<String, Long> e : spent.entrySet()) {            long cap = limit.getOrDefault(e.getKey(), 0L);            out.append(e.getKey()).append(' ').append(e.getValue()).append(' ')               .append(cap).append(' ').append(cap - e.getValue()).append('\n');        }        System.out.print(out);    }}

C#Main.cs · 41 줄

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int c = int.Parse(Console.ReadLine().Trim());        var limit = new Dictionary<string, long>();        var spent = new SortedDictionary<string, long>(StringComparer.Ordinal); // 열쇠를 글자 코드 순으로        for (int i = 0; i < c; i++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            limit[p[0]] = long.Parse(p[1]);            spent[p[0]] = 0;        }        int n = int.Parse(Console.ReadLine().Trim());        long total = 0; // 3,000 × 10억 = 3조라 int로는 넘친다        var sb = new StringBuilder();        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            long amount = long.Parse(p[1]);            long cap = limit.GetValueOrDefault(p[0], 0); // 예산을 정하지 않은 항목은 한도 0            long before = spent.GetValueOrDefault(p[0], 0);            long after = before + amount;            spent[p[0]] = after;            total += amount;            sb.Append(total).Append(' ').Append(after);            if (before <= cap && after > cap) sb.Append(" over");            sb.Append('\n');        }        foreach (var (name, s) in spent)        {            long cap = limit.GetValueOrDefault(name, 0);            sb.Append($"{name} {s} {cap} {cap - s}\n");        }        Console.Write(sb);    }}

C++main.cpp · 38 줄

#include <iostream>#include <map>#include <string> int main() {    std::ios::sync_with_stdio(false);    int c, n;    std::cin >> c;    std::map<std::string, long long> limit;    std::map<std::string, long long> spent; // std::map은 열쇠를 정렬해 둔다    for (int i = 0; i < c; i++) {        std::string name;        long long cap;        std::cin >> name >> cap;        limit[name] = cap;        spent[name] = 0;    }    std::cin >> n;    long long total = 0; // 3,000 × 10억 = 3조라 int로는 넘친다    std::string out;    for (int i = 0; i < n; i++) {        std::string name;        long long amount;        std::cin >> name >> amount;        // count로 먼저 묻는다: limit[name]이라고 읽으면 없는 열쇠가 0으로 새로 생긴다        long long cap = limit.count(name) ? limit[name] : 0;        long long before = spent[name]; // 없으면 []가 0으로 만들어 준다        long long after = before + amount;        spent[name] = after;        total += amount;        out += std::to_string(total) + " " + std::to_string(after) + (before <= cap && after > cap ? " over" : "") + "\n";    }    for (const auto& [name, s] : spent) {        long long cap = limit.count(name) ? limit[name] : 0;        out += name + " " + std::to_string(s) + " " + std::to_string(cap) + " " + std::to_string(cap - s) + "\n";    }    std::cout << out;}

Cmain.c · 50 줄

#include <stdio.h>#include <stdlib.h>#include <string.h> /* C에는 사전이 없다: 항목은 많아야 100개라 이름 표를 차례로 찾는다 */typedef struct {    char name[11];    long long limit, spent; /* 3,000 × 10억 = 3조라 int로는 넘친다 */} Item; static Item items[100];static int count = 0; static int find_or_add(const char* name) {    for (int i = 0; i < count; i++)        if (strcmp(items[i].name, name) == 0) return i;    strcpy(items[count].name, name);    items[count].limit = 0; /* 예산을 정하지 않은 항목은 한도 0 */    items[count].spent = 0;    return count++;} static int by_name(const void* a, const void* b) {    return strcmp(((const Item*)a)->name, ((const Item*)b)->name);} int main(void) {    int c, n;    char name[11];    long long x;    scanf("%d", &c);    for (int i = 0; i < c; i++) {        scanf("%10s %lld", name, &x);        items[find_or_add(name)].limit = x;    }    scanf("%d", &n);    long long total = 0;    for (int i = 0; i < n; i++) {        scanf("%10s %lld", name, &x);        Item* it = &items[find_or_add(name)];        long long before = it->spent;        it->spent += x;        total += x;        printf("%lld %lld%s\n", total, it->spent, before <= it->limit && it->spent > it->limit ? " over" : "");    }    qsort(items, count, sizeof items[0], by_name);    for (int i = 0; i < count; i++)        printf("%s %lld %lld %lld\n", items[i].name, items[i].spent, items[i].limit, items[i].limit - items[i].spent);    return 0;}

Craykonmain.cray · 43 줄

c = 콘솔.줄읽기().수로변환();limit = 사전();spent = 사전();반복 (i = 0; i < c; i++){    p = 콘솔.줄읽기().공백제거().나누기();    limit[p[0]] = p[1].수로변환();    spent[p[0]] = 0;}n = 콘솔.줄읽기().수로변환();total = 0;반복 (i = 0; i < n; i++){    p = 콘솔.줄읽기().공백제거().나누기();    name = p[0];    amount = p[1].수로변환();    // 없는 열쇠를 읽으면 멈추니 먼저 넣어 둔다(예산을 정하지 않은 항목은 한도 0)    만약 (!limit.있나(name))    {        limit[name] = 0;    }    만약 (!spent.있나(name))    {        spent[name] = 0;    }    before = spent[name];    spent[name] = before + amount;    total = total + amount;    row = total + " " + spent[name];    만약 (before <= limit[name] && spent[name] > limit[name])    {        row = row + " over";    }    콘솔.쓰기(row);} // 열쇠목록은 넣은 차례라 사전 순으로 정렬한다names = spent.열쇠목록;names.정렬();각각 (name 에서 names){    콘솔.쓰기(name + " " + spent[name] + " " + limit[name] + " " + (limit[name] - spent[name]));}