백준 32387 (C++) 충전하기

최초 업로드: 2025-09-24 21:33:30

최근 수정 시간: 2025-09-28 15:00:26

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 충전하기

[문제 링크](https://www.acmicpc.net/problem/32387)

## 문제 설명

동우는 다양한 전자기기를 사용한다. 수많은 전자기기의 충전기를 모두 들고 다니는 것이 번거로웠던 동우는 $N$개의 포트가 있는 멀티 포트 충전기를 장만했다. 동우의 멀티 포트 충전기는 특이하여 각 포트별로 출력해주는 전력이 다르다. 구체적으로 동우가 구매한 멀티 포트 충전기의 $i$번 포트는 $i$만큼의 전력을 출력해준다.

동우는 다양한 전자기기로 작업을 하면서 총 $Q$번 충전기에 꽂거나 뽑을 것이다. 구체적으로 동우가 하는 행동은 $2$가지로 아래와 같은 입력으로 주어진다.

<ul>
	<li><code>1</code> $i$: 최소 전력이 $i$인 전자기기를 $i$번 포트에 꽂는다. 만약 $i$번 포트에 전자기기가 꽂혀 있다면, 현재 남아 있는 최소 전력 이상의 포트 중 가장 전력이 작은 포트에 기기를 꽂는다. 만약 남아 있는 모든 포트가 최소 전력 미만이라면, 기기를 꽂지 않는다.</li>
	<li><code>2</code> $i$: $i$번 포트에 기기가 꽂혀 있다면 기기를 뽑는다.</li>
</ul>

이때, 각 행동에 대해 다음을 출력하라.

<ul>
	<li><code>1</code>번 행동: 성공적으로 전자기기를 꽂았다면 포트의 번호를 출력하며, 꽂지 않았다면 <code>-1</code>을 출력한다.</li>
	<li><code>2</code>번 행동: 기기가 꽂혀 있었다면 몇 번째 행동에서 꽂힌 기기인지 출력하며, 꽂혀 있지 않았다면 <code>-1</code>을 출력한다. 여기서 몇 번째 행동인지는 <code>1</code>번과 <code>2</code>번을 행동을 합쳐서 센다.</li>
</ul>

## 입력

첫 번째 줄에 포트의 수 $N(1\leq N\leq 10^{6})$과 행동의 수 $Q(1\leq Q\leq 10^{6})$가 주어진다.

두 번째 줄부터 $Q$줄에 걸쳐 동우가 하는 행동의 타입 $t(t\in\{ 1,2 \})$와 포트 번호 또는 최소 전력을 의미하는 정수 $i(1\leq i\leq N)$가 공백으로 구분되어 주어진다.

## 출력

각각의 행동이 주어질 때마다 행동의 결과를 한 줄에 하나씩 출력한다.

## 풀이
처음에 모든 포트를 셋에 넣어 놓고, 1번 행동에서 lower_bound를 사용해 사용 가능한 포트를 빼낸다. 2번 행동에서는 이미 사용한 포트라면 셋에 다시 넣어준다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int used[1'000'001];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;

set<int> port;
 for(int i=1;i<=n;i++) {
 port.insert(i);
 used[i]=-1;
 }

for(int tc=1;tc<=q;tc++) {
 int t, i; cin >> t >> i;
 if(t==1) {
 auto p = port.lower_bound(i);
 if(p!=port.end()) {
 cout << *p << '\n';
 port.erase(p);
 used[*p]=tc;
 } else {
 cout << "-1\n";
 }
 } else {
 cout << used[i] << '\n';
 port.insert(i);
 used[i]=-1;
 }
 }
}
```