[G5] 백준 1092번 배 C++ 큐, 맵, 이진 탐색, 그리디 알고리즘

리뷰

 

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

그리디 문제지만 여러가지 자료 구조와 알고리즘을 접목하여 푼 문제

주어지는 화물이 1만개 이하이므로 이진 탐색 메서드를 통해 O(LogN) 내로 풀이가 가능하다.

 

 

전역 변수

• n : 주어지는 크레인의 개수
• m : 주어지는 화물의 개수
• ans : 정답을 저장하기 위한 변수
• mc : 크레인의 max값을 저장하기 위한 변수
• mb : 화물의 max값을 저장하기 위한 ㅂ젼수
• wait : 현재 턴에 아직 사용하지 않은 크레인을 저장할 정수 타입의 큐
• used : 현재 턴에 사용한 크레인을 저장할 정수 타입의 큐
• boxes : 화물 정보를 저장하기 위한 정수 key와 정수 value타입의 맵

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 크레인 정보를 받아 mc에 최대값을 저장하고 wait에 크레인 정보를 추가한다.
2. boxes의 기본값 0을 key로 value를 아무거나 넣어준다. (크레인이 일을 할 수 있는지 체크용)
3. m값을 입력 받고 m개의 화물 정보를 받아 mb에 최대값을 저장하고 boxes에 화물 무게를 key로 추가해 준다.
4. 만약 mc가 mb보다 작을 경우 모든 박스를 배로 옮길 수 없으므로 -1를 출력하고 중단해 준다.
5. 모든 박스를 배로 옮길 수 있다면 while문에 ans를 전위증가 시킨 값을 넣어 루프를 생성한다.
6. 매 턴마다 만약 wait가 비지 않았고 boxes의 size가 1보다 클 경우 while루프를 하나 더 실행한다.
7. wait큐에서 크레인 정보를 하나 빼주고 정수형 변수 now로 초기화 해준다.
8. upper_bound메서드를 통해 boxes에서 now보다 큰 key의 반복자를 it으로 초기화 해준다.
9. it을 전위 감소 시켜준 후 key값이 0이 아니면서, 그 값이 now보다 작거나 같으면 다음 로직을 실행한다.
10. 맵에서 해당 key의 value를 감소시켜준 뒤에 used 큐에 now를 추가해 준다.
11. 만약 value가 0이 되었을 경우(해당 무게의 화물을 모두 처리한 경우) 맵 상에서 해당 반복자를 제거해 준다.
12. 위 작업을 마친 후 boxes의 size가 1이 되었을 경우 루프를 종료한다.
13. 아닐 경우 wait와 used를 swap하여 used에 있는 크레인들을 다시 wait로 옮겨준다.
14. break 처리될 때 까지 ans를 증가시키며 위 작업을 계속 진행해 준다.

 

참고 사항

1. 그리디하게 접근하면 각 크레인이 화물을 옮길 수 있는 무게 범위 내에서 가장 큰 화물을 옮겨야 한다.
2. 추가로, 같은 무게의 화물이 들어올 수 있으므로 오름 차순으로 정렬되어 있는 map자료구조를 사용해 주었다.
3. map은 오름차순 정렬되어 있기 때문에 upper_bound메서드를 통해 그리디한 값을 찾아낼 수 있다.
4. upper_bound를 통해 해당 크레인이 처리할 수 있는 화물을 찾고 반복자를 1번 내려주면 해결할 수 있는 화물이다.
5. 화물을 입력 받기 전에 boxes의 key가 0인 요소를 추가해 준 이유가 여기서 나온다.
6. 만약 upper_bound에서 찾아낸 반복자를 감소 시켰는데 해당 값이 0이면 해당 크레인은 더 이상 작업할 수 없다.
7. 이 경우에는 used큐에 넣어주지 않는다면 다음 탐색시에는 해당 크레인의 정보를 참조하지 않게 된다.
8. 따라서 위 로직은 upper_bound를 통해 O(LogN)의 시간 복잡도로 문제를 처리할 수 있게 된다.

 

정답 코드

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

int n, m, ans, mc, mb;

queue<int> wait;
queue<int> used;
map<int, int> boxes;

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

	cin >> n;
	while (n--) {
		int a; cin >> a;
		mc = max(mc, a);
		wait.push(a);
	}

	boxes[0] = 1;
	cin >> m;
	while (m--) {
		int a; cin >> a;
		mb = max(mb, a);
		boxes[a]++;
	}

	if (mc < mb) {
		cout << -1;
		return 0;
	}

	while (++ans) {
		while (!wait.empty() && boxes.size() > 1) {
			int now = wait.front(); wait.pop();
			auto it = boxes.upper_bound(now);
			
			if ((*--it).first != 0 && (*it).first <= now) {
				(*it).second--;
				used.push(now);
				if (!(*it).second) boxes.erase(it);
			}
		}
		if (boxes.size() == 1) break;
		swap(wait, used);
	}
	cout << ans;
}