[Algorithm]Baekjoon 1092번 :: 배

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

1092번: 배

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
vector<int> crainWeights;
vector<int> boxWeights;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        int num;
        cin >> num;
        crainWeights.push_back(num);
    }
 
    sort(crainWeights.rbegin(), crainWeights.rend());
 
    cin >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int num;
        cin >> num;
        boxWeights.push_back(num);
    }
 
    sort(boxWeights.rbegin(), boxWeights.rend());
 
    if (crainWeights[0] < boxWeights[0])
    {
        cout << -1;
        return 0;
    }
 
    int count = 0;
 
    while (!boxWeights.empty())
    {
        ++count;
 
        for (int i = 0; i < crainWeights.size(); ++i)
        {
            for (int j = 0; j < boxWeights.size(); ++j)
            {
                if (crainWeights[i] >= boxWeights[j])
                {
                    boxWeights.erase(boxWeights.begin() + j);
                    break;
                }
            }
        }
    }
 
    cout << count;
}

 

가장 먼저 생각할 수 있는 투박한(?) 코드.

사실 erase를 직접적으로 쓰는 경우는 거의 없긴하다. 중간요소를 삭제하면 나머지 뒤의 요소를 땡겨야해서 그렇다.

근데 인풋최대값이 작아서 그런가, 통과는 한다. 

박스무게가 최대 1만개이니, erase를 1만번 수행한다 가정했을 때 처음 erase하면 9999번, 그다음 9998번 .... 하다가 계속 줄어들테니, 대략 1부터 9999까지 더하는거랑 비슷하니 50,000,000번으로 주어진 시간제한안에 통과할 수 있긴 하다.

실제로 코드 제출하면 대충 890ms대정도 나왔다. 

 

근데 반드시 더 시간효율이 좋은 풀이가 있을거라 생각했다. 말했다시피 erase를 사용해서 투박하게짜는건 조금만 인풋값이 커져도 너무 시간이 늘어나기 때문에, 딱 필요한곳에서만 쓰는 풀이가 아니라면 다른풀이로도 접근해봐야 한다.

 

사실 이 풀이도 생각하기 어렵지 않은 풀이긴하다. 제거한 박스는 따로 체크해서 넘어가는식인데, 딱딱 필요한만큼만 진행하는식이 아닌 마찬가지로 처음부터 체크하는건 마찬가지다만, 과정과정마다 수행하는 코드가 간결하기 때문에 상관없나보다. erase하는것보다 11배정도 더 빠르다.

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
vector<int> crainWeights;
vector<int> boxWeights;
bool check[10000] = { false };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        int num;
        cin >> num;
        crainWeights.push_back(num);
    }
 
    sort(crainWeights.rbegin(), crainWeights.rend());
 
    cin >> m;
 
    for (int i = 0; i < m; ++i)
    {
        int num;
        cin >> num;
        boxWeights.push_back(num);
    }
 
    sort(boxWeights.rbegin(), boxWeights.rend());
 
    if (crainWeights[0] < boxWeights[0])
    {
        cout << -1;
        return 0;
    }
 
    int count = 0;
    int mCount = 0; // 박스제거카운팅.
 
    while (1)
    {
        ++count;
        int nIndex = 0;
        
        for (int i = 0; i < m; ++i)
        {
            if (!check[i] && crainWeights[nIndex] >= boxWeights[i])
            {
                check[i] = true;
                ++nIndex;
                ++mCount; 
 
                if (nIndex == n) break;
            }
        }
        
        if (mCount == m) break;
    }
 
    cout << count;
}