[프로그래머스]level.2 - 택배 상자(C++)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131704

프로그래머스

첫번째 풀이

첫번째는 그리디로 풀었는데 vector.erase()를 반복문으로 사용해야 해서 시간 초과가 났다.

list를 사용하여 erase 시간 복잡도를 줄인다고 해도, list는 index를 이용한 랜덤 액세스가 불가능하기 때문에 코드가 복잡해지고 원하는 인덱스에 접근하기까지 시간이 오래걸린다.

게다가 생각하기도 힘든 풀이이다.

틀린 풀이이기 때문에 간단하게만 설명하면,

현재 박스가 순서에 맞는 박스라면 boxs에서 삭제한다. 아니라면 다음 박스를 가리킨다.

만약 이전 박스가 다음 순서의 박스라면 이전 박스를 가리킨다.

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

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    vector<int> boxs(order);
    sort(boxs.begin(), boxs.end());

    int box_idx = order[0]-1;
    int order_idx = 0;

    while (!boxs.empty())
    {
        if (box_idx == boxs.size())
            break;

        if (boxs[box_idx] == order[order_idx])
        {
            boxs.erase(boxs.begin() + box_idx);
            ++order_idx;
            ++answer;
        }
        else
            ++box_idx;

        if (box_idx - 1 >= 0 && boxs[box_idx - 1] == order[order_idx])
        {
            --box_idx;
        }
    }

    return answer;
}

두번째 풀이

두번째 풀이는 스택을 이용했다.

sub 컨베이어를 stack으로 설정하고, 박스를 하나씩 컨베이어 벨트에 넣는다.

만약 가장 최근에 넣은 박스가 현재 순서에 맞는 박스라면 컨베이어에서 꺼내고 다음 순서의 박스를 찾는다.

만약 가장 최근에 넣은 박스에 순서에 맞지 않는 박스라면 컨베이어 밸트에 박스를 넣고 현재 순서를 유지한다.

#include <vector>
#include <stack>

using namespace std;

int solution(vector<int> order) {
    int answer = 0;
    stack<int> sub;

    // 첫번째 박스 넣기
    int num = 1;
    sub.push(num);

    for (int i = 0; i < order.size(); ++i)
    {
        // sub 컨테이너의 가장 나중에 들어온 박스가 순서에 맞는 박스라면
        if (!sub.empty() && sub.top() == order[i])
        {
            // 컨테이너에서 박스 빼기
            sub.pop();
            // 정답 개수 추가
            ++answer;
        }

        // 순서에 맞는 박스가 아니라면
        else
        {
            // 박스의 수 초과시 더 이상 컨테이너에 박스 추가 안한다
            if (num >= order.size()) break;

            // 컨테이너에 박스 추가
            ++num;
            sub.push(num);

            // 박스 순서 유지
            --i;
        }
    }

    return answer;
}