[BOJ/Gold 3] 백준 29618 미술 시간(C++)

문제 링크

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

29618번: 미술 시간

 

문제

민규는 어느 날 문득 그림이 그리고 싶어졌다. 마침 옆에는 미술과 PS에 통달한 정환이 백준 문제를 풀고 있었다. 민규는 정환에게 그림 잘 그리는 법을 물어보았고, 정환은 길이가 N칸인 긴 직사각형 모양의 색칠되지 않은 종이를 주며 다음과 같은 자신의 지시를 따르면 멋진 그림이 완성될 것이라고 얘기했다.

• a b x: a번째 칸부터 b번째 칸까지, 색칠되지 않은 칸을 x번째 색으로 칠한다.

하지만 민규는 이 과정이 너무 지루해 누군가 대신해 주길 바라고 있다. 여러분이 대신 민규의 그림을 완성해 주자.

 

입력

첫째 줄에 칸의 개수 N (1 ≤ N ≤ 10^5)과 쿼리의 개수 Q (1 ≤ Q ≤ 10^5)가 공백으로 구분되어 주어진다.

둘째 줄부터 Q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ a ≤ b ≤ N; 1 ≤ x ≤ 10^9)

 

출력

모든 쿼리를 수행한 후 각 칸의 색을 한 줄에 공백을 사이에 두고 출력한다. 이때 색칠되지 않은 칸은 0을 출력한다.

 

예제 입력 1

6 2
4 4 3
1 5 1

예제 출력 1

1 1 1 3 1 0

 

알고리즘 분류

• 자료 구조

 

풀이

Set을 사용해서 원소 관리를 O(logN)에 걸쳐서 수행한다.

1부터 N까지 Set에 insert하고, Q번의 쿼리를 수행하면서 A부터 B번째 칸까지 X번째 색으로 칠하는데, 색칠한 칸의 Index는 Set에서 erase하면 된다.

lower_bound를 이용해 A 이상의 원소에 해당하는 칸을 계속 찾아서 해당 칸에 X번째 색을 칠하는데, 원소가 존재하지 않는다면 이미 색칠한 칸임을 뜻한다. 그리고 원소가 B를 초과하게 되면 탐색을 멈춘다.

이렇게 최대 N개의 원소를 제거하게 되므로 시간 복잡도는 O(NlogN)만큼 걸리게 된다.

 

코드

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

using namespace std;
int N, Q, A, B, X;
set<int> S;
int Answer[MAX];

void init() {
    for (int i = 1; i <= N; i++) {
        S.insert(i);
    }
}

void settings() {
    while (!S.empty()) {
        auto Iterator = S.lower_bound(A);
        int Now = *Iterator;
        if ((Now > B) || (Now < A)) {
            break;
        }
        Answer[Now] = X;
        S.erase(Now);
    };
}

void input() {
    cin >> N >> Q;
    init();
    for (int i = 0; i < Q; i++) {
        cin >> A >> B >> X;
        settings();
    }
}

void find_Answer() {
    for (int i = 1; i <= N; i++) {
        cout << Answer[i] << " ";
    }
    cout << "\n";
}

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

    return 0;
}