백준 - 32387

요즘 따끈따끈한 대회 문제를 푸는 재미에 빠져 거의 하루에 6시간씩 알고리즘 문제를 해결하는 것 같다

 

핵심요소

<세그트리>

 

 

문제를 처음 본 뒤 가장 핵심적인 요소는 i 번째 뒤에 있는 요소 즉 i ~ n 까지의 포트중 사용할수 있는 가장 작은 포트를 찾는 것이라는 것을 파악한뒤 세그트리를 이용하여 logn 시간안에 찾으면 되겠다는 생각이 들었다

 

물론 개인적으로 처음에는 브루드포스로 해결해 보는 경향이 있어 일단 구현 해보았지만 역시 시간 초과가 발생하였다

 

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<queue>

#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

typedef long long ll;

struct RMQ {
	int n;
	vector<int> rangeMin;

	RMQ(const vector<int>& array) {
		n = array.size();
		rangeMin.resize(n * 4);
		init(array, 0, n - 1, 1);
	}

	int init(const vector<int>& array, int left, int right, int node) {
		if (left == right) return rangeMin[node] = array[left];
		int mid = (left + right) / 2;
		int leftMin = init(array, left, mid, node * 2);
		int rightMin = init(array, mid + 1, right, node * 2 + 1);
		return rangeMin[node] = min(leftMin, rightMin);
	}

	int query(int left, int right, int node, int nodeLeft, int nodeRight) {
		if (right < nodeLeft || nodeRight < left) return 1000001;
		if (left <= nodeLeft && nodeRight <= right) return rangeMin[node];
		int mid = (nodeLeft + nodeRight) / 2;
		return min(query(left, right, node * 2, nodeLeft, mid),
						query(left, right, node * 2 + 1, mid + 1, nodeRight));
	}

	int query(int left, int right) {
		return query(left, right, 1, 0, n - 1);
	}

	int update(int index, int newValue, int node, int nodeLeft, int nodeRight) {
		if (index < nodeLeft || nodeRight < index) return rangeMin[node];
		if (nodeLeft == nodeRight) return rangeMin[node] = newValue;
		int mid = (nodeLeft + nodeRight) / 2;
		return rangeMin[node] = min(update(index, newValue, node * 2, nodeLeft, mid),
													update(index, newValue, node * 2 + 1, mid + 1, nodeRight));
	}
};

int main() {
	Fast;
	int n, q;
	cin >> n >> q;

	vector<int> arr(n);
	//행동 번지를 저장한다;
	vector<int> answer(n);
	for (int i = 0; i < n; i++) {
		arr[i] = i + 1;
	}

	RMQ rmq(arr);
	
	for (int i = 1; i <= q; i++) {
		int t, cost;
		cin >> t >> cost;

		if (t == 1) {
			// 제거
			int index = rmq.query(cost - 1, n - 1) - 1;
			//더이상 자리가 없음
			if (index == 1000000) {
				cout << -1 << '\n';
				continue;
			}
			answer[index] = i;
			cout << index + 1 << '\n';
			rmq.update(index, 1000001, 1, 0, n - 1);
		}
		else {
			// 추가
			if(answer[cost - 1] == 0)
				cout << -1 << '\n';
			else {
				cout << answer[cost - 1] << '\n';
				answer[cost - 1] = 0;
				rmq.update(cost - 1, cost, 1, 0, n - 1);
			}
		}
	}
	
	return 0;
	
}

 

후기

항상 문제를 푼뒤에 나보다 빠른 시간안에 푼 사람들의 코드를 확인하는데 segTree를 비트연산을 사용하여 구성하는 방법을 보고 역시 아직 갈길이 멀구나 라는 생각이 들었다