[Programmers] Lv2. 택배상자 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

문제에서 스택(Stack) 쓰라고 대놓고 제시해줘서, 스택 썼습니다. 다만, order 길이가 백만 개라 시간 초과가 날까 걱정했는데 안 나더라구요. 아무래도 실을 수 없는 경우가 생기기에 백만 개를 다 보지 않아서 그런가 봅니다.

저는 다음 순서를 통해 코드를 작성하였습니다.

 

• 현재 택배 상자 번호 == order[i]라면, answer + 1을 해줍니다.
• 현재 택배 상자 번호 < order[i]라면, order[i] - 1까지 스택에 넣어주고 answer + 1을 해줍니다. 그 후, 현재 택배 상자 번호 = order[i] + 1로 갱신시켜 줍니다.
• 현재 택배 상자 번호 > order[i]라면, 스택의 top과 order[i]와 비교합니다.
  • 같다면 answer + 1을 해주고, pop을 합니다.
  • 아니라면 더 이상 실을 수 있는 택배가 없으므로 answer을 리턴합니다.
• 현재 택배 상자 번호가 마지막 택배 상자 번호(order.size())를 넘어간다면, 스택에 모두 쌓인 상태이므로 answer에 스택 크기만큼 더하고 리턴합니다.

 

✏️소스 코드 및 결과

#include <vector>
#include <stack>
using namespace std;

int solution(vector<int> order) {
	int answer = 0;
	int deliveryBox = 1;
	stack<int> subContainer;

	for (const auto requiredOrder : order) {
		if (order.size() < deliveryBox) {
			answer += subContainer.size();
			break;
		}

		if (deliveryBox == requiredOrder) {
			deliveryBox++;
			answer++;
			continue;
		}

		if (deliveryBox < requiredOrder) {
			while (deliveryBox < requiredOrder) subContainer.emplace(deliveryBox++);
			answer++;
			deliveryBox++;
			continue;
		}

		if (deliveryBox > requiredOrder and !subContainer.empty()) {
			if (subContainer.top() == requiredOrder) {
				answer++;
				subContainer.pop();
				continue;
			}
			break;
		}
	}

	return answer;
}