[BOJ] 18866번 : 젊은 날의 생이여 C++ 풀이

N개의 u, v가 주어진다. 구하고 싶은 값은 K인데 i < K, K < j라고 할때 ui > uj, vi < vj를 만족하는 K를 구해야 한다.

K를 기준으로 생각해보자. K의 왼쪽과 오른쪽을 기준으로 가장 큰값과 가장 작은 값들만 전처리 해놓는다면, O(1)에 K가 조건을 만족하는지 알 수 있을 것이다. 왜냐면 결국 왼쪽에서 가장 큰값이 오른쪽에서 가장 작은값보다 클때 무조건 정답이 될 수 있기 때문이다.

그래서 O(N) 탐색 두번을 통해 왼쪽, 오른쪽을 기준으로 최소 최대값을 전처리하고, 전처리한 값을 기준으로 K를 찾으면 된다. 시간복잡도는 O(N)이 소요된다.

#include <bits/stdc++.h>
#define MINF 0x7f7f7f7f
#define INF 2000000000
#define MOD 10007
#define NUM 100010
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
int N, answer = -1;
int r[2][1000010], k[2][1000010], h[1000010], s[1000010];

void init() {
    cin >> N;
    for (int i=1; i<=N; i++) {
        cin >> h[i] >> s[i];
    }
    for (int i=1; i<=N; i++) {
        r[0][i] = h[i], r[1][i] = s[i];
        k[0][i] = h[i], k[1][i] = s[i];
        
        if (r[0][i] == 0) {
            r[0][i] = -INF;
            k[0][i] = INF;
        }
        if (r[1][i] == 0) {
            r[1][i] = INF;
            k[1][i] = -INF;
        }
    }

    for (int i=N-1; i>=1; i--) {
        r[0][i] = max(r[0][i], r[0][i+1]);
        r[1][i] = min(r[1][i], r[1][i+1]);
    }
    for (int i=2; i<N; i++) {
        k[0][i] = min(k[0][i], k[0][i-1]);
        k[1][i] = max(k[1][i], k[1][i-1]);
        
    }

    for (int i=1; i<N; i++) {
        if (k[0][i] > r[0][i+1] && k[1][i] < r[1][i+1]) answer = i;
    }

    cout << answer << '\n';
} 

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init();
}