글 읽기 - 프린터 큐 시간초과

gkswns3708 3년 전 0

다른 사람 코드를 봐도 거의 비슷한 컨셉으로 만들어서

시간 초과가 어디서 일어나는지 잘 모르겠습니다...

한번 지적해 주시면 감사하겠습니다.

#include <cstdio>
#include <utility>
#include <queue>
#pragma warning(disable:4996)

using namespace std;



int main() {
	queue<pair<int,int>> que;
	int num;
	int N, M;
	int tempnum;
	scanf("%d", &num);
	
	for (int i = 0; i < num; i++) {
		int arr[10] = { 0, };
		int count;
		int max;
		//문서수 N 위치 M
		scanf("%d %d", &N, &M);
		for (int j = 0; j < N; j++) {
			scanf("%d", &tempnum);
			//pair는 중요도, 처음 위치 저장
			que.push(make_pair(tempnum, j));
			arr[tempnum]++;
		}
		
			while (1) {
				for (int i = 9; i >= 1; i--) {
					if (arr[i] != 0) {
						max = i;
						break;
					}
				}
				if (que.front().first == max) {
					if (que.front().second == M) {
						count++;
						printf("%d\n", count);
						break;
					}
					que.pop();
					count++;
					arr[max]--;
				}
				else {
					que.push(que.front());
					que.pop();
				}
			}	
	}
}

p_ce1052 3년 전 1

각 테스트케이스 시작시에 큐의 size를 출력해서 확인해보세요.

gkswns3708 3년 전 0

원하는 순서의 값이 pop되는 순간 다음 que들의 push에 의해 que가 더 쌓이고 있었네요.

남은 que.size()만큼 pop시켜 해결했습니다.

ghkd3531 11달 전 0

큐를 비워주는 코드를 넣어서 문제 해결했습니다. 감사합니다. 그런데 왜 큐를 비우느냐에 따라 결과가 달라지나요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

프린터 큐 시간초과

gkswns3708 3년 전 0

p_ce1052 3년 전 1

gkswns3708 3년 전 0

ghkd3531 11달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말