[백준/C++] 1092번. 배

문제

1092번: 배

---

1. 첫 번째 풀이 (마지막 풀이)

사고 과정

- 크레인과 박스를 내림차순 정렬한 후, 각 배열의 첫 번째 원소를 비교한다.

- 크레인으로 들 수 있다면 해당 박스를 지우고, 없다면 다음 박스를 비교한다.

- 크레인이 한 번씩 움직이면 1분을 추가한다.

 

1. crain, box 배열에 입력받음

2. for문(i)을 생성, 크레인을 한 번씩 돌림. 종료 후 i를 출력

3. for문(j)을 생성, 모든 크레인을 한 번씩 순회함

4. for문(k)을 생성, 모든 박스를 비교하며 들 수 있다면 해당 박스 삭제

 

코드

#include <cstdio>
#include <vector>
#include <algorithm>

int main() {
	int n, m, temp, i;
	std::vector<int> crain, box;

	scanf("%d", &n);
	while (n--) {
		scanf("%d", &temp);
		crain.push_back(temp);
	}

	scanf("%d", &m);
	while (m--) {
		scanf("%d", &temp);
		box.push_back(temp);
	}

	std::sort(crain.begin(), crain.end(), std::greater<>());
	std::sort(box.begin(), box.end(), std::greater<>());

	if (crain[0] < box[0]) {
		printf("-1");
		return 0;
	}

	for (i = 0; box.size() != 0; i++) {
		for (int j = 0; j < crain.size(); j++) {
			if (box.size() == 0) {
				break;
			}
			for (int k = 0; k < box.size(); k++) {
				if (box[k] <= crain[j]) {
					box.erase(box.begin() + k);
					break;
				}
			}
		}
	}

	printf("%d", i);
}

 

결과

시간 초과를 예상했는데 생각보다 싱겁게 성공했다.

---

개선

사고 과정

- 알고리즘적으로 손볼 곳이 있을까?

- 정렬 후 그리디하게 옮긴다는 로직은 더 최적화할 수 없어보인다.

- 개선 가능한 부분은 정렬과 반복문 정도?

- 입력과 동시에 정렬하려면 힙을 쓰는 게 좋아 보인다. 힙과 벡터를 비교해 볼까?

 

힙: 값 추가 시 O(log n), 값 삭제 시 O(log n)

벡터: 값 추가 시 O(1), 값 삭제 시 O(n), 값 정렬 시 O(nlog n)

 

- 만약 힙을 쓴다면, 지금 비교하는 부분은 어떻게 변하는가? 그리고 완전 내림차순 정렬이 되는가?

- 완전한 그리디 구현이 어려워 보인다. 오히려 벡터가 더 나을지도.

- erase 대신 bool 벡터를 추가로 생성해 제외하는 방식도 떠올렸다.

- 오름차순으로 정렬 후 끝에서부터 정리해 나가는 건 어떨까?

- erase는 앞쪽의 원소를 제거할수록 비용이 크다. 오름차순으로 정렬 후 끝자리를 제거하면 비용을 줄일 수 있을 것 같다.

- 반복문을 압축하기도 방법이 떠오르지 않는다. 이 코드가 내가 낼 수 있는 최선인 것 같다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/1150530

imagine9님의 코드

내 코드와 비교

1. l을 마지막에 한 번만 출력했으며, if else 문을 통해 못 옮기는 경우를 제하셨다.

2. 입력받을 때 n, m을 보존했다. 이어 시간을 세는 for문에서  i < m을 조건식으로 사용하셨다.

3. 나는 모든 크레인을 순환하며 박스와 비교했고, imagine9님은 모든 박스를 순환하며 크레인과 비교했다.

4. t로 크레인이 옮긴 박스를 카운트하며, t[j]가 l(현재까지 걸린 시간)보다 작을 때만 1 증가시키며 while문을 탈출했다. 뒤집어 말하자면, 해당 크레인이 이미 박스를 옮긴 크레인일 경우 다음 크레인을 탐색한다.

5. 그렇게 모든 박스를 옮겼을 때 l을 출력

그리고 나보다 훨씬 빠르게 연산에 성공하셨다.

---

강평

소스 코드 분석이 꽤나 어려웠다. 중간에 chatGPT의 도움을 받아 어찌저찌 해석에 성공했다. 그래도 결국 박스가 기준이냐, 크레인이 기준이냐만 달랐을 뿐 전체적인 구조는 비슷했다. 그럼에도 시간은 큰 차이를 보였는데, erase 함수의 비용이 컸던 걸로 예상된다.