[G4] 백준 31792한빛미디어 (Hard) C++ 트리 셋, 이분 탐색

리뷰

 

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

트리 맵과 lower_bound를 활용한 문제

 

 

전역 변수

• q : 쿼리의 개수를 저장할 변수
• dic : 책의 가격을 저장할 트리 셋
• cnt : 가격별 책의 개수를 저장할 배열

 

함수

없음

 

 

문제풀이

1. q값을 입력 받고, q번의 while 루프를 수행 하고 매 루프마다 변수 op에 값을 입력 받아준다.
2. op가 3이 아닌 경우 책의 가격을 변수 price에 입력 받아 저장해 준다.
3. op가 1인 경우 dic에 price가 존재한다면 cnt의 price를 1만큼 증가시켜 준다.
4. dic에 price가 존재하지 않으면 dic에 price를 insert해주고, cnt의 price를 1만큼 증가시켜 준다.
5. op가 2인 경우 dic에 price가 존재한다면 cnt의 price를 1만큼 감소시키고, 0이 되었다면 dic에서 price를 erase해준다.
6. op가 3인 경우 변수 cnt를 0으로, 반복자 it을 dic의 begin()으로 초기화 해준다.
7. it이 dic의 end()에 도달할 때 까지 while 루프를 수행해 준다.
8. 매 루프마다 cnt를 증가시키고, 현재 이터레이터의 값의 두배를 lower_bound하여 it을 갱신해 준다.
9. while루프가 종료된 후에 cnt에 저장된 값을 출력해 준다.

 

트러블 슈팅

• 트리 셋이 아닌 트리 맵으로 접근, lower_bound를 일반 메서드로 수행, 배열 대신 unordered_map을 사용 하였다가 시간 초과를 받았다.
• 트리 셋의 lower_bound를 사용해 주고, 해시 맵 대신 배열을 사용해 주니 AC를 받았다.

 

참고 사항

• 가격의 범위가 최대 100만이라 배열로도 충분히 cnt를 관리할 수 있다.

 

정답 코드

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

int q;
set<int> dic;
int cnt[1000001];

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

	cin >> q;
	while (q--) {
		int op; cin >> op;
		if (op != 3) {
			int price; cin >> price;
			if (op == 1) {
				if (dic.count(price)) cnt[price]++;
				else {
					dic.insert(price);
					cnt[price]++;
				}
			}
			else {
				if (dic.count(price)) {
					if (!--cnt[price]) dic.erase(price);
				}
			}
		}
		else {
			int cnt = 0;
			auto it = dic.begin();
			while (it != dic.end()) {
				cnt++;
				int price = *it;
				it = dic.lower_bound(price * 2);
			}
			cout << cnt << "\n";
		}
	}
}