[BOJ/C++] 1092: 배

🏅 GOLD 5

✏️ 1차 솔루션

1. 크레인 무게 제한 내림차순으로 vector 에 저장
2. 상자 무게 우선순위 큐에 저장 ➡️ 내림차순 정렬
3. 모든 상자를 실을 때까지 상자를 크레인에 배정하는 과정 반복 ➡️ 가장 무거운 상자가 가장 무게제한 큰 크레인에 배정됨
   1) 현재 크레인에 넣을 수 있는 상자를 찾을 때까지 현재 크레인에 넣을 수 없는 상자는 다음 차례로 넘기기 위해 delay 큐에 저장
   ❗️무게 제한이 가장 큰 크레인부터 넣을 수 없다면 그 상자는 아예 실을 수 없으므로 -1 return
   2) 현재 크레인에 넣을 수 있는 상자를 찾으면 현재 회차에 크레인에 실을 상자가 있다고 exist 표시하고 크레인을 모두 돌았을 때 exist 가 true 이면 시간 count
   3) 상자 배정 과정에서 모든 상자를 다 넣었다면 현재까지 시간 count return

🚨 1차 trouble

시간초과. 풀이과정도 너무 복잡하고 loop 가 많아서 이미 예상한 결과..

✏️ 최종 솔루션

⭐️ 방법은 동일

1. 크레인과 박스를 vector 에 받아서 내림차순 정렬
2. 가장 무거운 박스가 크레인보다 무거우면 -1
3. 박스를 모두 옮길 때까지 while 문으로 상자 옮기기
   1) 각 크레인마다 무거운 상자부터 실을 수 있는 상자 탐색해서 상자를 실을 수 있으면 box 에서 지우고 exist 표시하고 현재 크레인과 박스 매칭은 종료
   2) 크레인 한바퀴 돌았을 때 실은 box가 있으면 time 늘려주기

📌 self feedback

⭐️ 큐 대신 vector 를 사용하는 것이 관건
항상 가장 무거운 상자를 먼저 넣기 위한 방법으로 vector 를 사용하려면 erase 를 사용하거나 존재여부를 체크하는 visit 배열을 따로 관리해야해서 우선순위 큐를 선택했는데 우선순위 큐를 사용하면 자동으로 정렬되기 때문에 크레인 for 문을 돌 때 크레인에 실는데 실패한 상자들을 관리하는 큐를 따로 두어야 하기 때문에 과정이 더 복잡해짐
❗️ 코드의 간결성을 생각한다면 vector 를 사용한 for 문이나 erase 사용도 고려한 유연한 선택 필요
❗️ 모든 상자를 실을 수 없는 경우는 가장 무거운 상자를 가장 무게제한이 큰 크레인에 실지 못하는 경우밖에 없음

✏️ 최종 code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n,m;
    cin >> n;
    
    vector<int> crain;
    for(int i=0;i<n;i++) {
        int k;
        cin >> k;
        crain.push_back(k);
    }
    
    cin >> m;
    
    vector<int> box;
    for(int i=0;i<m;i++) {
        int k;
        cin >> k;
        box.push_back(k);
    }
    
    sort(crain.begin(),crain.end(),greater<>());
    sort(box.begin(),box.end(),greater<>());
    
    if(box[0]>crain[0]) {
        cout << -1 << endl;
        return 0;
    }
    
    int ans=0;
    
    while (!box.empty()) {
        bool exist=false;
        for(int i=0;i<n;i++) {
            for(int j=0;j<box.size();j++) {
                if(crain[i]>=box[j]) {
                    box.erase(box.begin()+j);
                    exist=true;
                    break;
                }
            }
        }
        
        if(exist) ans++;
        
    }
    
    cout << ans << endl;
        
}