[G4] 백준 29811번 지각하기 싫어 C++ 멀티셋

리뷰

 

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

인구 수가 중복이 되는지 여부를 알 수 없어 멀티셋을 사용하여 풀이하였다.

 

 

전역 변수

• MAX : 배열 크기의 최대값을 저장할 상수 변수
• n : 애지문에서 대운동장까지의 경로 수를 저장할 변수
• m : 대운동장에서 ITBT관까지의 경로 수를 저장할 변수
• k : 쿼리의 개수를 저장할 변수
• N : 애지문에서 대운동장까지의 경로의 인구를 저장할 배열
• M : 대운동장에서 ITBT관까지의 경로의 인구를 저장할 배열
• NV : 애지문에서 대운동장까지의 경로의 인구와 인덱스를 오름차순으로 정렬할 멀티셋
• MV : 대운동장에서 ITBT관까지의 경로의 인구와 인덱스를 오름차순으로 정렬할 멀티셋

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받는다.
2. 1 ~ n까지의 인구수를 N배열에 입력 받고, NV에는 인구수와 인덱스를 쌍을 지어 추가해 준다.
3. 1 ~ m까지의 인구수를 M배열에 입력 받고, MV에는 인구수와 인덱스 + n을 쌍을 지어 추가해 준다.
4. k값을 입력 받고, k번의 루프를 수행한다. 매 루프마다 변수 op에 쿼리 종류를 입력 받아준다.
5. op가 U라면 변수 a, b에 인덱스와 값을 입력 받아준다.
6. a이 n이하일 경우 NV에서 N[a], a값을 erase하고, N[a]를 b로 바꾼 다음 NV에 b, a를 insert해준다.
7. a이 n초과일 경우 MV에서 M[a - n], a값을 erase하고, M[a - n]를 b로 바꾼 다음 MV에 b, a를 insert해준다.
8. op가 L이라면 NV의 begin()의 인덱스 값과 MV의 begin()의 인덱스 값을 공백을 구분하여 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 가장 빠른 길이 여러가지일 경우 인덱스가 작은 값을 출력해 주어야 한다.
• 우선순위 큐를 2개를 사용하고, lazy하게 delete해주는 방법도 가능할 것 같다.

 

정답 코드

#include<iostream>
#include<set>
using namespace std;

const int MAX = 100001;
int n, m, k;
int N[MAX], M[MAX];
multiset<pair<int, int>> NV, MV;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> N[i];
		NV.insert({ N[i], i });
	}
	for (int i = 1; i <= m; ++i) {
		cin >> M[i];
		MV.insert({ M[i], i + n });
	}

	cin >> k;
	while (k--) {
		char op; cin >> op;
		if (op == 'U') {
			int a, b; cin >> a >> b;
			if (a <= n) {
				NV.erase({ N[a], a });
				N[a] = b;
				NV.insert({ b, a });
			}
			else {
				MV.erase({ M[a - n], a });
				M[a - n] = b;
				MV.insert({ b, a });
			}
		}
		else {
			cout << (*NV.begin()).second << " " << (*MV.begin()).second << "\n";
		}
	}
}