백준 16405번 Birthday Boy [C++]

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

#한국어 번역

Bobby는 새 회사에 입사했고, 인사팀에서 그의 생일을 사무실 달력에 기록하도록 요청했습니다. Bobby the Birthday Boy는 특별하게 느끼고 싶어 합니다! 또한, Bobby the Birthday Boy는 주목받기 위해 거짓말을 하는 것을 꺼려하지 않습니다.

그는 사람들이 생일을 축하하지 않거나 케이크를 먹지 않은 기간이 길어질수록 새로운 생일이 찾아올 때 더 좋아한다는 것을 알아챘습니다. 그래서 가능한 한 긴 생일이 없는 기간이 막 끝난 시점에 자신의 생일을 정하고 싶어 합니다. 물론, 그는 동료들과 생일을 공유하고 싶지 않습니다.

Bobby가 가능한 한 특별하게 느낄 수 있도록 가짜 생일을 만들어 줄 수 있나요? Bobby는 윤년에 신경 쓰지 않습니다: 모든 해가 윤년이 아니며, 아무도 2월 29일에 생일이 없다고 가정할 수 있습니다. 만약 여러 날짜가 동일한 경우, Bobby는 현재 날짜인 10월 27일 직후에 오는 날짜를 선택하기로 결정했습니다. 이는 가능한 한 빨리 생일을 축하할 수 있기 때문입니다.

입력

첫 줄에 1 ≤ n ≤ 100, Bobby가 새 사무실에 있는 동료의 수가 주어집니다.

그 다음 n개의 줄이 이어지며, 각 줄은 한 동료에 해당합니다. 각 줄은 동료의 이름(최대 20개의 대소문자)과 생일 날짜가 공백으로 구분되어 주어집니다. 날짜는 mm-dd 형식입니다.

출력

Bobby가 선택한 가짜 생일 날짜(mm-dd 형식)를 출력하세요.

 

 

 

#문제 간단 정리

구현 + 시뮬레이션 문제

 

#문제 해결 방법

구현 시뮬레이션 문제이기 때문에 지문 그대로 구현하면 된다만..

 

예외 조건이 은근 있기 때문에 신경써야된다.

우선 입력에서 파싱을 사용해서 입력받아야되는걸 생각하고 

    // 동료들의 생일을 일수로 변환하여 저장
    for(int i = 0; i < n; i++) {
        string name, day;
        cin >> name >> day;
        int month = stoi(day.substr(0, 2));
        int d = stoi(day.substr(3, 2));
        dayto365.push_back(makeDays(month, d));
    }

우선 간격을 계산하기 위해서

월 일로 되어있는 걸

365일 기준으로 환산해주고

그걸 다시 월 일로 바꿔주는 함수를 만들자.

// 각 월의 일수 (비윤년 기준)
int daysInMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 날짜를 일수로 변환하는 함수 (1~365)
int makeDays(int month, int day) {
    int result = 0;
    for(int i = 0; i < month - 1; i++) {
        result += daysInMonth[i];
    }
    result += day;
    return result;
}

// 일수를 "mm-dd" 형식으로 변환하는 함수
string day_to_date(int day_number) {
    int month = 1;
    while(day_number > daysInMonth[month - 1]) {
        day_number -= daysInMonth[month - 1];
        month++;
    }
    // 월과 일을 두 자리로 포맷팅
    string mm = (month < 10 ? "0" : "") + to_string(month);
    string dd = (day_number < 10 ? "0" : "") + to_string(day_number);
    return mm + "-" + dd;
}

 

여기서 중요한건 각 월을 배열로 저장해줘야 환산이 쉬워진다.

 

자 그렇다면 이렇게 환산한날들을 정렬해주고 

 

    // 생일을 정렬
    sort(dayto365.begin(), dayto365.end());

    // 연말을 넘어가는 경우를 처리하기 위해 첫 번째 생일에 365를 더해 추가
    dayto365.push_back(dayto365[0] + 365);

 

자 for 문을 돌면서 i-1 번째랑 비교해서 그 간격을 조사할건데

첫번째 인덱스 0 번은 i-1 번이 없기 때문에 365 를 더해서 뒤로 더해준다.

이렇게하면 전부 비교가 가능하다

int maxGap = -1;
    vector<int> candidates;

    // 가장 긴 간격을 찾고, 그 간격의 끝날(다음 생일 전날)을 후보로 추가
    for(int i = 1; i < dayto365.size(); i++) {
        int tempGap = dayto365[i] - dayto365[i - 1] - 1; // 생일 사이의 기간

        if(tempGap > maxGap){
            maxGap = tempGap;
            candidates.clear();

            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            // 동료의 생일과 겹치지 않는지 확인
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
        else if(tempGap == maxGap){
            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
    }

 

자 이렇게 돌면서 만약에 같은 날짜가 생긴다면 

벡터에다 넣어서 동점인 날짜를 계산하기 위해 처리를 해준다

만약 겹치는 생일이 있으면 넣지 않는다 (이부분이 테스트케이스에 있는지 모르겠다.)

 

만약 현재 maxGap 과 같다면 벡터에 추가해서 나중에 처리하도록한다

 

다시 maxGap이갱신된다면 벡터를 clear해주고 넣어주자

// 현재 날짜인 10월 27일의 일수
    int the1027 = makeDays(10, 27);

    // 후보 날짜 중 10월 27일 이후의 날짜를 찾기 위한 처리
    vector<int> after1027;
    for(auto date : candidates){
        if(date > the1027){
            after1027.push_back(date);
        }
        else{
            after1027.push_back(date + 365); // 연말을 넘어가는 경우 처리
        }
    }

    int selected_date;
    if(!after1027.empty()){
        // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택
        selected_date = *min_element(after1027.begin(), after1027.end());
    }
    else{
        // 없다면 모든 후보 중 가장 빠른 날짜 선택
        selected_date = *min_element(candidates.begin(), candidates.end());
    }

 

이제 후보 날짜를 처리해 줄건데(동점인경우)

 

10/27일을 365단위로 환산해두고 일단

10/27일보다 작은경우 365를 더해서 벡터에 넣어준다.

int selected_date;
    if(!after1027.empty()){
        // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택
        selected_date = *min_element(after1027.begin(), after1027.end());
    }
    else{
        // 없다면 모든 후보 중 가장 빠른 날짜 선택
        selected_date = *min_element(candidates.begin(), candidates.end());
    }

    // 연말을 넘어간 날짜는 다시 1년으로 환산
    if(selected_date > 365){
        selected_date -= 365;
    }

    // 결과 날짜를 "mm-dd" 형식으로 변환하여 출력
    string result_date = day_to_date(selected_date);
    cout << result_date << endl;

그중에서 제일 작은걸 찾은 다음에

만약 365를 넘으면 빼서 정상화 해준뒤에

 

날짜 형식을 바꿔서  출력한다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 각 월의 일수 (비윤년 기준)
int daysInMonth[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 날짜를 일수로 변환하는 함수 (1~365)
int makeDays(int month, int day) {
    int result = 0;
    for(int i = 0; i < month - 1; i++) {
        result += daysInMonth[i];
    }
    result += day;
    return result;
}

// 일수를 "mm-dd" 형식으로 변환하는 함수
string day_to_date(int day_number) {
    int month = 1;
    while(day_number > daysInMonth[month - 1]) {
        day_number -= daysInMonth[month - 1];
        month++;
    }
    // 월과 일을 두 자리로 포맷팅
    string mm = (month < 10 ? "0" : "") + to_string(month);
    string dd = (day_number < 10 ? "0" : "") + to_string(day_number);
    return mm + "-" + dd;
}

int main(){
    int n;
    cin >> n;
    vector<int> dayto365;

    // 동료들의 생일을 일수로 변환하여 저장
    for(int i = 0; i < n; i++) {
        string name, day;
        cin >> name >> day;
        int month = stoi(day.substr(0, 2));
        int d = stoi(day.substr(3, 2));
        dayto365.push_back(makeDays(month, d));
    }

    // 생일을 정렬
    sort(dayto365.begin(), dayto365.end());

    // 연말을 넘어가는 경우를 처리하기 위해 첫 번째 생일에 365를 더해 추가
    dayto365.push_back(dayto365[0] + 365);

    int maxGap = -1;
    vector<int> candidates;

    // 가장 긴 간격을 찾고, 그 간격의 끝날(다음 생일 전날)을 후보로 추가
    for(int i = 1; i < dayto365.size(); i++) {
        int tempGap = dayto365[i] - dayto365[i - 1] - 1; // 생일 사이의 기간

        if(tempGap > maxGap){
            maxGap = tempGap;
            candidates.clear();

            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            // 동료의 생일과 겹치지 않는지 확인
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
        else if(tempGap == maxGap){
            int candidate_date = dayto365[i] - 1;
            if(candidate_date == 0) candidate_date = 365;
            if(find(dayto365.begin(), dayto365.end() -1, candidate_date) == dayto365.end() -1){
                candidates.push_back(candidate_date);
            }
        }
    }

    // 현재 날짜인 10월 27일의 일수
    int the1027 = makeDays(10, 27);

    // 후보 날짜 중 10월 27일 이후의 날짜를 찾기 위한 처리
    vector<int> after1027;
    for(auto date : candidates){
        if(date > the1027){
            after1027.push_back(date);
        }
        else{
            after1027.push_back(date + 365); // 연말을 넘어가는 경우 처리
        }
    }

    int selected_date;
    if(!after1027.empty()){
        // 10월 27일 이후의 날짜 중 가장 빠른 날짜 선택
        selected_date = *min_element(after1027.begin(), after1027.end());
    }
    else{
        // 없다면 모든 후보 중 가장 빠른 날짜 선택
        selected_date = *min_element(candidates.begin(), candidates.end());
    }

    // 연말을 넘어간 날짜는 다시 1년으로 환산
    if(selected_date > 365){
        selected_date -= 365;
    }

    // 결과 날짜를 "mm-dd" 형식으로 변환하여 출력
    string result_date = day_to_date(selected_date);
    cout << result_date << endl;

    return 0;
}