백준 2457 공주님의 정원 c++

문제를 보고 그리디로 풀 수 있겠다는 생각이 들었다.
중간 중간에 조건 잡는 것이 꽤나 까다로웠지만 잘 풀었다고 생각했는데,,
90%에서 시간초과가 났다.

중간에 idx를 기록해서 for문 탐색 시간을 최대한 줄여보려 했지만,
아마 pair<int, int>를 두 개나 가지고 있는 t배열을 sort하는 과정이 시간 초과의 원인이라 판단했다.
sort하지 않으면 idx를 기록하는 것 또한 무의미하기 때문에 다른 방법을 찾아야 했다.

시간초과 코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

pair<pair<int, int>,pair<int, int>> t[100002];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    pair<int, int> cur = {0, 0};
    for(int i = 0; i < n; i++) {
        cin >> t[i].X.X >> t[i].X.Y >> t[i].Y.X >> t[i].Y.Y;
        // 꽃이 지는 날이 3월 2일 이하이면서 가장 늦게 지는 꽃 탐색
        if(t[i].X.X < 3) cur = max(cur, t[i].Y);
        else if(t[i].X.X == 3 && t[i].X.Y == 1) cur = max(cur, t[i].Y);
    }
    // 조건에 맞는 꽃 없으면 종료
    if(!cur.X) {
        cout << 0; return 0;
    }
    int idx = 0, ans = 1;
    sort(t, t+n);
    while(cur.X <= 11 && idx < n) {
        int i = 0;
        pair<int, int> temp = cur;
        for(i = idx; i < n; i++) {
            if(t[i].X <= cur) {
                temp = max(temp, t[i].Y);
                idx = i+1;
            }
            else break;
        }
        if(idx == i) {
            cur = temp;
            ans++;
        }
    }
    if(cur.X < 12) {
        cout << 0; return 0;
    }
    cout << ans;
}

해결과정

최대 40만개의 int data를 sort하지 않고 해결할 수 있는 방법을 찾아야 했다.
일단 꽃이 피는 날과 지는 날을 보여주는 4개의 데이터를 2개의 int data로 간단화하는 것부터 시작했다.

예를 들어 2월 15일에 피고 3월 23일에 지는 꽃의 데이터를 215, 323으로 바꿔주고, 시작 조건인 3월 1일과 마지막 날짜인 12월 1일을 301, 1201로 바꿔줬다.

초기 시작값을 301로 시작하는 cur의 값이 1201이 미만일 때까지 while문을 돌리고
그 안에서 적절한 조건을 넣어 다음 시간 값인 temp를 업데이트 해준다.
temp값이 cur과 같다면 0을 출력하고 종료한다.

해결 코드

/*
    최소개수의 꽃을 선택 => 겹치는 날이 최소로 적어야 한다.
    즉 3월 1일부터 11월 30일까지 개화하는 꽃이 겹치는 개수가 최소로 적어야 한다.
    꽃이 지는 날이 3월 2일 이하이면서 가장 오래 피는 꽃을 시작으로
    마지막 꽃이 지는 날이 최소 12월 1일인 꽃으로 마무리(12월1일에 지면 11월 30일까지 개화시기)
*/
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

vector<pair<int, int>> t;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 0; i < n; i++) {
        int sm, sd, em, ed;
        cin >> sm >> sd >> em >> ed;
        // 날짜 단순화 작업
        t.push_back({sm*100+sd, em*100+ed});
    }
    int cur = 301, ans = 0;
    while(cur < 1201) {
        int temp = cur;
        // 현재 저장된 꽃의 지는 날이 지금 확인하는 꽃의 피는날보다 앞에 있어야 중간에 비지 않는다.
        // for문을 돌리면서 temp 값을 계속해서 업데이트 해주기 때문에 
        // t[i].X <= cur 조건을 만족하는 꽃들 중에서 지는 날이 가장 늦는 꽃을 선택할 수 있다.
        for(int i = 0; i < n; i++) {
            if(t[i].X <= cur && t[i].Y > temp) temp = t[i].Y;
        }
        // 조건에 맞는 꽃이 없기 때문에 종료
        if(temp == cur) {
            cout << 0; return 0;
        }
        ans++;
        cur = temp;
    }
    cout << ans;
}

후기

• 데이터 수가 많고 시간제한이 1초라면 sort는 최대한 사용하지 말자.
• 주어진 input data를 최대한 단순화해보자.