열쇠 있나사전으로 세기합계P0179

작은 도서관 대출 장부

작은 도서관은 책마다 한 권씩만 있고, 대출과 반납을 한 줄씩 장부에 적는다. 첫 줄에 기록 수 q가, 다음 q줄에 기록 "out 날 책" 또는 "in 날 책"이 주어진다. 날은 도서관을 연 날을 0으로 센 정수이고, 기록은 날이 줄지 않는 순서로 주어진다. "out d b"는 d일에 책 b를 빌려 주는 기록이다. 그 책이 이미 빌려 간 상태라면 "busy b"를 한 줄 출력하고 이 기록은 없던 것으로 한다. 그렇지 않으면 책 b는 d일부터 빌려 간 상태가 되고, 책 b의 대출 횟수가 1 늘어난다. "in d b"는 d일에 책 b를 돌려받는 기록이다. 그 책이 빌려 간 상태가 아니라면 "unknown b"를 한 줄 출력하고 이 기록은 없던 것으로 한다. 그렇지 않으면 빌려 간 날이 s일 때 d − s일 동안 빌린 것이고, 책 b는 다시 도서관에 있는 상태가 된다. 빌린 날수가 14일 이하면 연체료가 없고, 14일을 넘으면 넘은 하루마다 100원의 연체료를 받는다. 모든 기록을 처리한 뒤 "fee 연체료합"을 한 줄 출력하라. 연체료합은 돌려받은 대출의 연체료를 모두 더한 값이고, 끝까지 돌려받지 못한 책은 넣지 않는다. 마지막 줄에는 대출 횟수가 가장 많은 책을 "top 책 횟수"로 출력하라. 횟수가 같은 책이 여럿이면 이름이 사전 순으로 앞선 책을 출력한다. 대출이 한 번도 없었으면 마지막 줄에 "top none"을 출력한다. 사전 순은 앞 글자부터 비교해 알파벳이 앞선 쪽이 앞서고, 한쪽이 다른 쪽의 앞부분이면 짧은 쪽이 앞선다.

입력: 1 ≤ q ≤ 10,000, 0 ≤ 날 ≤ 1,000,000(정수, 줄지 않음).
책 이름은 영어 소문자 1 ~ 10글자이고 서로 다른 책은 1,000권 이하.
첫 낱말은 out 또는 in
출력: busy·unknown 줄을 기록 순서대로 출력하고, 이어서 "fee 연체료합"과 "top 책 횟수"(또는 "top none")

예시 1 · stdin

8
out 1 moby
out 3 dune
out 5 moby
in 15 moby
in 20 dune
out 20 dune
in 40 emma
in 50 dune

stdout

busy moby
unknown emma
fee 1900
top dune 2

예시 2 · stdin

4
out 0 atlas
out 0 atlas
in 16 atlas
in 16 atlas

stdout

busy atlas
unknown atlas
fee 200
top atlas 1

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

입력(stdin)

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

$ 준비됐어요

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

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

사전 두 개를 써요.
빌려 간 책 → 빌려 간 날 사전으로 열쇠가 있는지 묻고, 책 → 대출 횟수 사전으로 세요.
열쇠가 있나: Python book in on_loan, JS·TS onLoan.has(book), Java containsKey, C# ContainsKey(빼면서 꺼내는 Remove(book, out int start)도 있어요), C++ find(book) != end(), 크레이콘 onLoan.있나(book).
C는 사전이 없어서 책 표를 차례로 찾고, 날이 0일 수 있으니 "빌려 가지 않음"을 −1로 둬요.
함정 하나: 0일에 빌린 책은 값이 0이라, Python if on_loan.get(book):나 JS if (onLoan.get(book))처럼 값의 참거짓으로 물으면 빌려 가지 않은 것으로 보여요.
열쇠가 있는지를 물어야 해요.
C++ if (onLoan[book])도 값으로 묻는 것이라 같은 함정이고, 게다가 없는 책을 0일로 새로 넣어 버려요.
세기: Python loans.get(book, 0) + 1, JS·TS (loans.get(book) ?? 0) + 1, Java merge(book, 1, Integer::sum), C# GetValueOrDefault(book, 0) + 1, C++ loans[book]++, 크레이콘은 있나로 0을 먼저 넣고 더해요.
함정 둘: Python Counter.most_common(1)은 횟수가 같으면 먼저 센 책을 줘서 사전 순이 아니에요.
min(loans, key=lambda b: (-loans[b], b))처럼 이름까지 비교하거나, Java TreeMap·C++ std::map처럼 열쇠 순으로 돌며 더 클 때만 바꿔요.
함정 셋: 연체료합은 1,000권 × 약 1억 원 = 약 1천억 원까지 가서 Java·C# int, C int로는 넘쳐요.
long·long long을 쓰고, Python·JS·TS·크레이콘은 2^53 안이라 그대로 돼요.
14일은 연체가 아니라서 max(0, 빌린날수 − 14) × 100이에요.

Pythonmain.py · 31 줄

import sys lines = sys.stdin.read().split("\n")q = int(lines[0])on_loan = {}      # 책 → 빌려 간 날loans = {}        # 책 → 빌려 간 횟수fee = 0out = []for line in lines[1:1 + q]:    kind, day, book = line.split()    day = int(day)    if kind == "out":        if book in on_loan:             # 빌려 간 날이 0일 수도 있으니 값이 아니라 열쇠가 있는지 묻는다            out.append(f"busy {book}")            continue        on_loan[book] = day        loans[book] = loans.get(book, 0) + 1    else:        if book not in on_loan:            out.append(f"unknown {book}")            continue        kept = day - on_loan.pop(book)        fee += max(0, kept - 14) * 100 out.append(f"fee {fee}")if loans:    best = min(loans, key=lambda b: (-loans[b], b))   # 많이 빌린 책, 같으면 사전 순으로 앞선 책    out.append(f"top {best} {loans[best]}")else:    out.append("top none")print("\n".join(out))

JavaScriptmain.js · 35 줄

const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const onLoan = new Map(); // 책 → 빌려 간 날const loans = new Map(); // 책 → 빌려 간 횟수let fee = 0;const out = [];for (const line of lines.slice(1, 1 + q)) {  const [kind, d, book] = line.trim().split(" ");  const day = Number(d);  if (kind === "out") {    // 빌려 간 날이 0이면 get()이 0이라 거짓이 된다: has()로 열쇠가 있는지 묻는다    if (onLoan.has(book)) {      out.push(`busy ${book}`);      continue;    }    onLoan.set(book, day);    loans.set(book, (loans.get(book) ?? 0) + 1);  } else {    if (!onLoan.has(book)) {      out.push(`unknown ${book}`);      continue;    }    const kept = day - onLoan.get(book);    onLoan.delete(book);    fee += Math.max(0, kept - 14) * 100;  }} out.push(`fee ${fee}`);let best = null;for (const [book, n] of loans) {  if (best === null || n > loans.get(best) || (n === loans.get(best) && book < best)) best = book;}out.push(best === null ? "top none" : `top ${best} ${loans.get(best)}`);console.log(out.join("\n"));

TypeScriptmain.ts · 40 줄

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const onLoan = new Map<string, number>(); // 책 → 빌려 간 날const loans = new Map<string, number>(); // 책 → 빌려 간 횟수let fee = 0;const out: string[] = [];for (const line of lines.slice(1, 1 + q)) {  const [kind, d, book] = line.trim().split(" ");  const day = Number(d);  if (kind === "out") {    // 빌려 간 날이 0이면 get()이 0이라 거짓이 된다: has()로 열쇠가 있는지 묻는다    if (onLoan.has(book)) {      out.push(`busy ${book}`);      continue;    }    onLoan.set(book, day);    loans.set(book, (loans.get(book) ?? 0) + 1);  } else {    const start = onLoan.get(book);    if (start === undefined) {      out.push(`unknown ${book}`);      continue;    }    onLoan.delete(book);    fee += Math.max(0, day - start - 14) * 100;  }} out.push(`fee ${fee}`);let best: string | null = null;let most = 0;for (const [book, n] of loans) {  if (best === null || n > most || (n === most && book < best)) {    best = book;    most = n;  }}out.push(best === null ? "top none" : `top ${best} ${most}`);console.log(out.join("\n"));

JavaMain.java · 44 줄

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 q = Integer.parseInt(br.readLine().trim());        Map<String, Integer> onLoan = new HashMap<>(); // 책 → 빌려 간 날        Map<String, Integer> loans = new TreeMap<>();  // 책 → 빌려 간 횟수(사전 순으로 돈다)        long fee = 0; // 1,000권 × 약 1억 원이라 int로는 넘친다        StringBuilder out = new StringBuilder();        for (int i = 0; i < q; i++) {            String[] p = br.readLine().trim().split(" ");            int day = Integer.parseInt(p[1]);            String book = p[2];            if (p[0].equals("out")) {                if (onLoan.containsKey(book)) {                    out.append("busy ").append(book).append('\n');                    continue;                }                onLoan.put(book, day);                loans.merge(book, 1, Integer::sum);            } else {                Integer start = onLoan.remove(book); // 없으면 null                if (start == null) {                    out.append("unknown ").append(book).append('\n');                    continue;                }                fee += Math.max(0, day - start - 14) * 100L;            }        }        out.append("fee ").append(fee).append('\n');        String best = null;        int most = 0;        for (Map.Entry<String, Integer> e : loans.entrySet()) {            if (e.getValue() > most) { // 사전 순으로 도니 같으면 앞의 것이 남는다                best = e.getKey();                most = e.getValue();            }        }        out.append(best == null ? "top none" : "top " + best + " " + most).append('\n');        System.out.print(out);    }}

C#Main.cs · 53 줄

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int q = int.Parse(Console.ReadLine().Trim());        var onLoan = new Dictionary<string, int>(); // 책 → 빌려 간 날        var loans = new Dictionary<string, int>();  // 책 → 빌려 간 횟수        long fee = 0; // 1,000권 × 약 1억 원이라 int로는 넘친다        var sb = new StringBuilder();        for (int i = 0; i < q; i++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            int day = int.Parse(p[1]);            string book = p[2];            if (p[0] == "out")            {                if (onLoan.ContainsKey(book))                {                    sb.Append($"busy {book}\n");                    continue;                }                onLoan[book] = day;                loans[book] = loans.GetValueOrDefault(book, 0) + 1;            }            else            {                if (!onLoan.Remove(book, out int start)) // 있으면 빼면서 값을 꺼낸다                {                    sb.Append($"unknown {book}\n");                    continue;                }                fee += Math.Max(0, day - start - 14) * 100L;            }        }        sb.Append($"fee {fee}\n");        string best = null;        int most = 0;        foreach (var (book, n) in loans)        {            if (best == null || n > most || (n == most && string.CompareOrdinal(book, best) < 0))            {                best = book;                most = n;            }        }        sb.Append(best == null ? "top none\n" : $"top {best} {most}\n");        Console.Write(sb);    }}

C++main.cpp · 36 줄

#include <algorithm>#include <iostream>#include <map>#include <string> int main() {    std::ios::sync_with_stdio(false);    int q;    std::cin >> q;    std::map<std::string, int> onLoan; // 책 → 빌려 간 날    std::map<std::string, int> loans;  // 책 → 빌려 간 횟수(열쇠 순으로 돈다)    long long fee = 0; // 1,000권 × 약 1억 원이라 int로는 넘친다    std::string out;    for (int i = 0; i < q; i++) {        std::string kind, book;        int day;        std::cin >> kind >> day >> book;        auto it = onLoan.find(book); // onLoan[book]으로 물으면 없는 책이 0일로 생겨 버린다        if (kind == "out") {            if (it != onLoan.end()) { out += "busy " + book + "\n"; continue; }            onLoan[book] = day;            loans[book]++;        } else {            if (it == onLoan.end()) { out += "unknown " + book + "\n"; continue; }            fee += std::max(0, day - it->second - 14) * 100LL;            onLoan.erase(it);        }    }    out += "fee " + std::to_string(fee) + "\n";    std::string best;    int most = 0;    for (const auto& [book, n] : loans)        if (n > most) { best = book; most = n; } // 사전 순으로 도니 같으면 앞의 것이 남는다    out += most == 0 ? "top none\n" : "top " + best + " " + std::to_string(most) + "\n";    std::cout << out;}

Cmain.c · 49 줄

#include <stdio.h>#include <string.h> /* C에는 사전이 없다: 책은 많아야 1,000권이라 책 표를 차례로 찾는다 */static char title[1000][11];static int out_day[1000];   /* 빌려 간 날, 빌려 가지 않았으면 -1 */static int loans[1000];     /* 빌려 간 횟수 */static int count = 0; static int find_or_add(const char* book) {    for (int i = 0; i < count; i++)        if (strcmp(title[i], book) == 0) return i;    strcpy(title[count], book);    out_day[count] = -1; /* 0일에 빌려 갈 수 있으니 "없음"은 -1로 둔다 */    loans[count] = 0;    return count++;} int main(void) {    int q;    scanf("%d", &q);    long long fee = 0; /* 1,000권 × 약 1억 원이라 int로는 넘친다 */    for (int e = 0; e < q; e++) {        char kind[4], book[11];        int day;        scanf("%3s %d %10s", kind, &day, book);        int b = find_or_add(book);        if (strcmp(kind, "out") == 0) {            if (out_day[b] >= 0) { printf("busy %s\n", book); continue; }            out_day[b] = day;            loans[b]++;        } else {            if (out_day[b] < 0) { printf("unknown %s\n", book); continue; }            int late = day - out_day[b] - 14;            if (late > 0) fee += late * 100LL;            out_day[b] = -1;        }    }    printf("fee %lld\n", fee);    int best = -1;    for (int i = 0; i < count; i++) {        if (loans[i] == 0) continue; /* 반납 기록만 있는 책은 빼고 */        if (best < 0 || loans[i] > loans[best] || (loans[i] == loans[best] && strcmp(title[i], title[best]) < 0))            best = i;    }    if (best < 0) printf("top none\n");    else printf("top %s %d\n", title[best], loans[best]);    return 0;}

Craykonmain.cray · 60 줄

q = 콘솔.줄읽기().수로변환();onLoan = 사전(); // 책 → 빌려 간 날loans = 사전(); // 책 → 빌려 간 횟수fee = 0;반복 (e = 0; e < q; e++){    p = 콘솔.줄읽기().공백제거().나누기();    day = p[1].수로변환();    book = p[2];    만약 (p[0] == "out")    {        만약 (onLoan.있나(book))        {            콘솔.쓰기("busy " + book);        }        아니면        {            onLoan[book] = day;            만약 (!loans.있나(book))            {                loans[book] = 0;            }            loans[book] = loans[book] + 1;        }    }    아니면 만약 (!onLoan.있나(book))    {        콘솔.쓰기("unknown " + book);    }    아니면    {        late = day - onLoan[book] - 14;        만약 (late > 0)        {            fee = fee + late * 100;        }        onLoan.빼기(book);    }}콘솔.쓰기("fee " + fee); best = 빈값;most = 0;각각 (book 에서 loans.열쇠목록){    n = loans[book];    만약 (best == 빈값 || n > most || n == most && book < best)    {        best = book;        most = n;    }}만약 (best == 빈값){    콘솔.쓰기("top none");}아니면{    콘솔.쓰기("top " + best + " " + most);}