인프런 커뮤니티 질문&답변

안녕하세요!

제가 queue와 구조체를 이용해 문제를 풀었는데 1초가 넘게 걸려서 무엇이 문제인지 질문합니다

queue의 push, pop은 O(1)이라고 알고 있는데도 이렇게 오래 걸려서..제가 유추하기로는 구조체를 썼기 때문인 것 같은데...만약 그렇다면 왜 그런 것인가요...?

코드 아래 첨부합니다.

#include<cstdio>
using namespace std;
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

int main(void)
{
	//cin.tie(NULL);  // 얘네 3줄은 iostream include했을 때 필요한 것.
	//cout.tie(NULL);
	//ios::sync_with_stdio(false);

	freopen("in4.txt", "rt", stdin);  // 파일 입력받음

	struct NumWork
	{
		int work;  // 작업 번호
		int t;     // 작업 시간
	};

	int n, k;
	scanf("%d", &n);

	queue<NumWork> work;
	for (int i = 0; i < n; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		work.push(NumWork{ i + 1, tmp });
	}
	scanf("%d", &k);

	int time = 0;  // 총 시간
	while (work.empty() == false)
	{
		if (time == k)  // 만약 k초면 break;
			break;

		NumWork now = work.front();
		work.pop();

		time++;  // 시간은 언제나 흐르므로 ++

		if (now.t - 1 == 0)  // 작업시간이 0됐으면 다시 queue에 넣지 않음
			continue;

		work.push(NumWork{ now.work, now.t - 1 });
	}
	if (work.empty())  // work가 empty면 모든 작업이 k이전에 끝난 것
		printf("-1");
	else               // empty가 아니면 k초 이후에 작업이 남아있었음
		printf("%d", work.front().work);
}