[BOJ] 백준 12791 Starman

출처: https://www.acmicpc.net/problem/12791

 Input 

1

1 2016

 

 Output 

25

1967 DavidBowie

1969 SpaceOddity

1970 TheManWhoSoldTheWorld

1971 HunkyDory

1972 TheRiseAndFallOfZiggyStardustAndTheSpidersFromMars

1973 AladdinSane

1973 PinUps

1974 DiamondDogs

1975 YoungAmericans

1976 StationToStation

1977 Low

1977 Heroes

1979 Lodger

1980 ScaryMonstersAndSuperCreeps

1983 LetsDance

1984 Tonight

1987 NeverLetMeDown

1993 BlackTieWhiteNoise

1995 1.Outside

1997 Earthling

1999 Hours

2002 Heathen

2003 Reality

2013 TheNextDay

2016 BlackStar

첫 번째 줄에 질의의 수 정수 Q(Q ≤ 100)가 주어진다.

이후 Q개의 줄에 질의 S, E(1 ≤ S ≤ E ≤ 2016)가 정수로 주어진다.

각 질의에 대해서 다음 정보를 출력한다

첫 번째 줄에는, 질의를 만족하는 데이빗 보위의 앨범 수 S를 출력한다.

이후 S개의 줄에 데이빗 보위의 앨범 이름을 새 줄로 구분하여 주어진 순서대로 출력한다.

 

앨범의 이름을 출력할 때,  띄어쓰기, 대소문자 등이 출제자의 코드와 다르게 출력되면 안 된다. 

출력은 예제에 나온 이름과 정확히 일치해야 한다. 각각의 질의마다 새 줄로 구분할 필요는 없다.

앨범을 출력할 때는, "발매연도 앨범 이름" (따옴표 없이) 의 형식으로 출력하라. 출력은 발매일 순으로 진행해야 하며,

 Input 

3

1973 1973

1977 1979

2014 2015

 

 Output 

2

1973 AladdinSane

1973 PinUps

3

1977 Low

1977 Heroes

1979 Lodger

0

David Bowie의 앨범과 발매년도는 변하지 않는 정보이기 때문에 Hash Map으로 Data를 구성한 다음

질의(Query)에 알맞는 정보를 출력하면 됩니다.

 

▶ [해시] Hash란?

[해시] Hash란?

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
 
int N;
map<int, vector<string>> info;
 
void init() {
    info[1967].push_back("DavidBowie");
    info[1969].push_back("SpaceOddity");
    info[1970].push_back("TheManWhoSoldTheWorld");
    info[1971].push_back("HunkyDory");
    info[1972].push_back("TheRiseAndFallOfZiggyStardustAndTheSpidersFromMars");
    info[1973].push_back("AladdinSane");
    info[1973].push_back("PinUps");
    info[1974].push_back("DiamondDogs");
    info[1975].push_back("YoungAmericans");
    info[1976].push_back("StationToStation");
    info[1977].push_back("Low");
    info[1977].push_back("Heroes");
    info[1979].push_back("Lodger");
    info[1980].push_back("ScaryMonstersAndSuperCreeps");
    info[1983].push_back("LetsDance");
    info[1984].push_back("Tonight");
    info[1987].push_back("NeverLetMeDown");
    info[1993].push_back("BlackTieWhiteNoise");
    info[1995].push_back("1.Outside");
    info[1997].push_back("Earthling");
    info[1999].push_back("Hours");
    info[2002].push_back("Heathen");
    info[2003].push_back("Reality");
    info[2013].push_back("TheNextDay");
    info[2016].push_back("BlackStar");
}
 
void input() {
    scanf("%d", &N);
}
 
void solve() {
    int s, e, cnt, i, j;
    while (N--) {
        scanf("%d %d", &s, &e);
        cnt = 0;
        for (i = s; i <= e; i++)
            cnt += info[i].size();
        printf("%d\n", cnt);
        for (i = s; i <= e; i++) {
            for (j = 0; j < info[i].size(); j++)
                cout << i << " " << info[i][j] << endl;
        }        
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    init();
    input();
    solve();
}

 

STL을 사용하지 않고 구현한 풀이는 아래 코드 참고

- Chaining 방식 구현

- 앨범(Node)의 총 개수 = 25개, Hash Table 크기 = 2016

- (동일한 년도의 앨범인 경우) Hash Map에 넣어줄 때는 리스트 앞쪽에 추가되므로 주의

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
void strcpy(char* dest, const char* src) {
    while (*dest++ = *src++);
}
 
struct Node {
    int year;
    char name[100];
    Node* next;
 
    Node* alloc(int year, const char* albumName, Node* np) {
        this->year = year, next = np;
        strcpy(name, albumName);
        return this;
    }
}buf[30], *htab[2020];
int bcnt, N;
 
void addMapInfo(int year, const char* name) {
    htab[year] = buf[bcnt++].alloc(year, name, htab[year]);
}
 
void init() {
    addMapInfo(1967, "DavidBowie");
    addMapInfo(1969, "SpaceOddity");
    addMapInfo(1970, "TheManWhoSoldTheWorld");
    addMapInfo(1971, "HunkyDory");
    addMapInfo(1972, "TheRiseAndFallOfZiggyStardustAndTheSpidersFromMars");
    addMapInfo(1973, "PinUps");
    addMapInfo(1973, "AladdinSane");
    addMapInfo(1974, "DiamondDogs");
    addMapInfo(1975, "YoungAmericans");
    addMapInfo(1976, "StationToStation");
    addMapInfo(1977, "Heroes");
    addMapInfo(1977, "Low");
    addMapInfo(1979, "Lodger");
    addMapInfo(1980, "ScaryMonstersAndSuperCreeps");
    addMapInfo(1983, "LetsDance");
    addMapInfo(1984, "Tonight");
    addMapInfo(1987, "NeverLetMeDown");
    addMapInfo(1993, "BlackTieWhiteNoise");
    addMapInfo(1995, "1.Outside");
    addMapInfo(1997, "Earthling");
    addMapInfo(1999, "Hours");
    addMapInfo(2002, "Heathen");
    addMapInfo(2003, "Reality");
    addMapInfo(2013, "TheNextDay");
    addMapInfo(2016, "BlackStar");
}
 
void input() {
    scanf("%d", &N);
}
 
void solve() {
    int s, e, cnt, i, j;
    while (N--) {
        scanf("%d %d", &s, &e);
        
        cnt = 0;
        for (i = s; i <= e; i++) {
            Node* p = htab[i];
            for (; p; p = p->next)
                cnt++;
        }
        printf("%d\n", cnt);
 
        for (i = s; i <= e; i++) {
            Node* p = htab[i];
            for (; p; p = p->next)
                printf("%d %s\n", p->year, p->name);
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    init();
    input();
    solve();
}