[BOJ/Gold 5] 백준 25603 짱해커 이동식(C++)

문제 링크

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

25603번: 짱해커 이동식

 

문제

짱해커 이동식은 상대방의 디스크에 자신의 이름을 남겨 자신이 왔다간 것을 알린다. 이동식에게 인정받기 위해 오늘도 수많은 기업들의 보안담당자들은 모의해킹 의뢰를 하기 위해 줄을 선다.

모든 의뢰를 받아들이기엔 너무 부담이 됐기 때문에, 각 의뢰들을 수행하는 데 필요한 비용을 측정해 최대한 비용이 적게 드는 의뢰들을 받으려 한다. 하지만, 의뢰를 연속으로 K번 이상 거절하면 이동식의 실력이 거품이었다는 소문이 나기 때문에, 임의의 연속된 K개의 의뢰 중에서 최소 하나 이상의 의뢰는 받아야 한다.

이동식은 가능한 낮은 비용이 드는 의뢰만 받고 싶어 한다. 즉, 수락한 의뢰들의 비용 중 최댓값을 최소화하려 한다. 기업 의뢰 리스트가 주어졌을 때, 위 조건을 만족하면서 의뢰를 수행할 때 수락한 의뢰들이 가진 비용 중 가장 높은 비용의 최솟값을 구해라. 단, 주어진 의뢰의 순서를 임의로 바꿀 수 없다.

입력

첫 번째 줄에 정수 N, K가 주어진다. (1 ≤ K < N ≤ 100,000)

두 번째 줄부터 N개의 기업 의뢰의 비용이 주어진다. 비용은 1 이상 10^9 이하의 정수이다.

출력

이동식이 수락한 의뢰들이 가진 비용 중 가장 높은 비용의 최솟값을 구해라.

예제 입력 1

5 2
1 3 5 4 2

예제 출력 1

4

예제 입력 2

8 3
1 100 100 1 1 100 100 1

예제 출력 2

1

예제 입력 3

8 2
1 100 100 1 1 100 100 1

예제 출력 3

100

알고리즘 분류

• 문자열
• 슬라이딩 윈도우

풀이

K개의 연속된 의뢰가 존재하는 구간의 최솟값의 최댓값을 구하는 문제이므로 슬라이딩 윈도우를 통해 각 구간별로 최솟값을 구한다.

최솟값을 구하기 위해 중복이 허용되고 자동적으로 정렬이 되는 multiset을 사용하였다.

set은 이진 트리 구조를 통해서 데이터를 관리하며, 데이터를 삽입 및 삭제를 할 때 O(logN)의 시간복잡도를 갖는다.

처음 K번의 데이터 삽입을 하고, N-K번 동안 데이터 삽입과 삭제를 1회씩 하기 때문에 2N - K번의 데이터 삽입 및 삭제가 이루어진다고 생각했고, O((2N - K)logN)의 시간복잡도를 가지며 N의 최댓값이 100,000이기 때문에, 최악의 경우라도 1초 이내에 연산이 가능하다고 판단하였다.

정렬이 자동적으로 되기 때문에 각 구간별로 최솟값은 multiset의 처음 원소이며, 이것은 begin()으로 해당 원소의 주소를 찾을 수 있으며 포인터를 통해 원소의 값을 구할 수 있다. 각 구간별로 최솟값을 비교해가면서 최댓값을 구한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#define MAX 100001
#define INF 2e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, K;
int MAP[MAX];
multiset<int> MS;
multiset<int>::iterator IT;
int Min = INF;
int Answer = 0;

void input() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> MAP[i];
    }
}

void settings() {
    for (int i = 0; i < K; i++) {
        int Now = MAP[i];
        MS.insert(Now);
    }
    Answer = max(Answer, *MS.begin());
    for (int i = K; i < N; i++) {
        int Prev = MAP[i - K];
        int Next = MAP[i];
        IT = MS.find(Prev);
        MS.erase(IT);
        MS.insert(Next);
        Answer = max(Answer, *MS.begin());
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}