[G5] 백준 30470번 호반우가 학교에 지각한 이유 3 C++ map, 트리맵, upper_bound

리뷰

 

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

스택 문제를 푸려고 들어왔는데 시간초과를 맞고 빨리 풀기 위해 Map으로 돌렸다.

 

 

전역 변수

• n : 쿼리의 개수를 저장할 변수
• dic : 현재 통나무의 길이별 개수를 저장할 map

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n번의 쿼리를 수행한다.
2. 매 쿼리마다 변수 op, v에 쿼리 정보를 입력 받는다.
3. op가 1인 경우 dic[v]를 1만큼 증가시킨다.
4. op가 2인 경우 dic이 빈 상태라면 continue처리한다.
5. 변수 b에 dic에서 가장 큰 key값을 저장한다.
6. 변수 t를 b-v와 0중 더 큰 값으로 저장한다.
7. 만약 t가 0인경우 dic을 clear처리하고, continue처리한다.
8. 변수 it에 dic에서 t를 기준으로 upper_bound한 이터레이터를 저장한다.
9. 변수 cnt를 0으로 초기화한다.
10. it이 end에 도달할때까지를 기준으로 하는 while루프를 수행한다.
11. cnt에 it의 value값을 더해주고, dic에서 it을 지워준다.
12. 이후 dic[t]의 value에 cnt만큼 값을 더해준다.
13. 모든 쿼리를 처리한 후 변수 sum을 0으로 초기화한다.
14. dic를 순회하며 sum에 key*value 값을 더해준다.
15. sum에 최종적으로 저장된 값을 출력한다.

 

트러블 슈팅

1. 스택에서 빼고 넣고 하는 과정에서 op가 2인 쿼리가 작정하고 들어온다면 시간 초과가 발생했다.
2. map을 통해 정렬 상태를 유지하여 각 길이의 개수를 저장하는 방식으로 풀이하여 AC를 받았다.

 

참고 사항

1. 통나무의 길이가 최대 10억까지 주어지므로 sum은 long long타입이어야 한다.
2. 스택이 정배인 문제인 것 같기는 한데 빠르게 풀기 위해 map을 선택하였다.

 

정답 코드

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

int n;
map< int, int > dic;

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

	cin >> n;
	while ( n-- )
	{
		int op, v; cin >> op >> v;
		if ( op == 1 )
			++dic[ v ];
		
		if ( op == 2 )
		{
			if ( dic.empty() )
				continue;

			int b = dic.rbegin()->first;
			int t = max( b - v, 0 );
			if ( t == 0 )
			{
				dic.clear();
				continue;
			}

			auto it = dic.upper_bound( t );
			int cnt = 0;
			while ( it != dic.end() )
			{
				cnt += it->second;
				it = dic.erase( it );
			}

			dic[ t ] += cnt;
		}
	}

	long long sum = 0;
	for ( const auto& [k, v] : dic )
		sum += ( long long )k * v;

	cout << sum;
}