[BOJ] 16305 - Birthday Boy

https://www.acmicpc.net/problem/16305

BOJ - Birthday Boy

문제 유형: 문자열 처리, 애드혹, 파싱, 정렬

문제 난이도: Gold V

시간 제한: 1초

메모리 제한: 512MB

 

문제

Bobby has just joined a new company, and human resources has asked him to note his birthday on the office calendar. Bobby the Birthday Boy wants to feel special! Also, Bobby the Birthday Boy does not mind lying for attention.

He notices that the longer people have not celebrated a birthday or eaten cake, the more they like it when a new one comes around. So he wants to pick his birthday in such a way that the longest period of time without a birthday possible has just passed. Of course he does not want to share his birthday with any colleague, either.

Can you help him make up a fake birthday to make him feel as special as possible? Bobby does not care about leap years: you can assume every year is not a leap year, and that no one has a birthday on the 29th of February. In case of a tie, Bobby decides to fill in the date that is soonest (strictly) after the current date, the 27th of October, because that means he will get to celebrate his birthday as soon as possible.

 

Bobby는 새로운 회사에 들어갔다.

인사팀에서 생일을 알려달라 하는데, 생일자가 없는 기간이 길어질수록 생일을 더 잘챙겨준다.

그래서, Bobby는 거짓말을 하고자 한다. 다른 동료들과 생일을 공유하고 싶지 않아하면서, 이전에 생일자가 없는 가장 긴 기간 이후의 생일을 말할 것이다.

빨리 보상을 받고싶기에, 같은 차이인 경우, 10월 27일 이후로부터 더 가까운걸 선호한다.

 

입력

• One line with a number 1 ≤ n ≤ 100, the number of colleagues Bobby has in his new office.
• Then follow n lines, each line corresponding to one coworker. Each line gives the name of the colleague (using at most 20 upper or lower case letters) separated from their birthday date by a space. The date is in format mm-dd.

첫째 줄에 n(1 ~ 100): 동료들의 수가 주어집니다.

이후 n개의 줄에는 동료의 이름과 생일정보다 주어집니다. 둘은 공백으로 구분됩니다. 날짜는 mm-dd꼴입니다.

 

출력

Print the fake birthday date (format: mm-dd) chosen by Bobby.

가짜 생일을 mm-dd꼴로 출력하시오.

 

풀이

날짜 데이터를 받아서 숫자로 변환하고 정렬하여, 이전 날짜로부터 가장 거리가 먼 날짜를 구한다.

그 날짜의 전날이 조건에 충족되는 날이다.

 

주의할 점은, 10-27이면 365일 기다려야 한다는 것이다.

이를 깔끔히 처리하면 된다.

 

정렬된 날짜들의 각각의 날짜를 순회하면서, 이전날로부터 가장 거리가 먼 날짜를 고른다.

0번날짜는 n-1번날짜로부터의 차이를 구하면 된다.

만약 차이가 같다면, 10-27일로부터 며칠 더 기다려야 하는지를 구해서, 그 값이 더 작은 걸로 골라서 tie-break를 처리하면 된다.

최종적으로 기존의 가장 오래기다리는 생일을 그렇게 구해서, 그 생일 전날을 mm-dd꼴로 변환하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

vector<int> prefixSumOfMonths = {0,   31,  59,  90,  120, 151, 181,
                                 212, 243, 273, 304, 334, 365};

int dayfrom(int a, int from) {
    int res = (a - from + 365) % 365;
    return res == 0 ? 365 : res;
}

string strdate(int day) {
    int lb =
        lower_bound(prefixSumOfMonths.begin(), prefixSumOfMonths.end(), day) -
        prefixSumOfMonths.begin();
    int date = day - prefixSumOfMonths[lb - 1];

    string m = to_string(lb);
    if (m.size() == 1) m = "0" + m;

    string d = to_string(date);
    if (d.size() == 1) d = "0" + d;

    return m + "-" + d;
}

int numday(string &date) {
    int month = (date[0] - '0') * 10 + date[1] - '0';
    int day = (date[3] - '0') * 10 + date[4] - '0';

    return prefixSumOfMonths[month - 1] + day;
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    string date = "10-27";
    int oct27 = numday(date);

    vector<int> birthdays;
    string temp;
    for (int i = 0; i < n; i++) {
        cin >> temp >> date;
        birthdays.emplace_back(numday(date));
    }
    sort(birthdays.begin(), birthdays.end());

    int maxDiffIdx = 0;
    int maxDiff = 365 - birthdays.back() + birthdays[0];
    int bestOffset = dayfrom(birthdays[0] - 1, oct27);
    for (int i = 1; i < n; i++) {
        int diff = birthdays[i] - birthdays[i - 1];
        int offset = dayfrom(birthdays[i] - 1, oct27);
        if (diff > maxDiff || (diff == maxDiff && offset < bestOffset)) {
            maxDiffIdx = i;
            maxDiff = diff;
            bestOffset = offset;
        }
    }

    int ans = birthdays[maxDiffIdx] - 1;
    if (ans == 0) ans = 365;
    cout << strdate(ans) << "\n";

    return 0;
}