글 읽기 - 프린터 큐 시간초과 질문드려요..

vvv3334 6년 전 0

프린트의 index와 중요도(pow)를 담는 배열을 선언하고 함수를 이용해서 큐처럼 사용하고 있습니다.

그리고 우선순위를 받아 내림차순 정렬 후, 우선순위와 같으면 큐에서 pop을 하고.

다르면 pop한 데이터를 바로 push해서 우선순위가 같아질 때 까지 반복합니다.

그리고 우선순위가 같아져서 pop이 된 경우에 찾아야할 index를 cnt를 이용하여 세는데 시간 초과가 나옵니다..

어떻게 더 최적화 할 수 있을까요?

#pragma warning(disable : 4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX (100+30)

int T;
int N, M;

int WP, RP;
int powArr[MAX];
int SP;

int Queindex[MAX];
int Quepow[MAX];
int RPi, RPp;



void input()
{
	int i, tmp;
	WP = RP = SP = RPi = RPp = 0;
	scanf("%d %d", &N, &M);
	for (i = 0; i < N; i++)
	{
		scanf("%d", &tmp);

		Quepow[WP] = tmp;
		Queindex[WP++] = i;
		powArr[SP++] = tmp;
	}
}


void Puship(int i, int p)
{
	//printf("RP WP : %d %d %d\n", RP, WP,QueNum);
	if (WP == N + 1) WP = 0;
	Queindex[WP] = i;
	Quepow[WP] = p;
	WP++;
}

int Popi()
{
	//printf("RP WP : %d %d %d\n", RP, WP,QueNum);
	if (RPi == N + 1) RPi = 0;
	return Queindex[RPi++];
}

int Popp()
{
	//printf("RP WP : %d %d %d\n", RP, WP,QueNum);
	if (RPp == N + 1) RPp = 0;
	return Quepow[RPp++];
}

int comp(const void *a, const void *b)
{
	return *(int*)a - *(int*)b;
}

int main(void)
{
	int i, j;

	int outSt;
	int cnt;

	int outi, outp;

	scanf("%d", &T);

	outi = outp = 0;
	for (i = 0; i < T; i++)
	{
		input();
		//output();
		qsort(powArr, N, sizeof(int), comp);
		//output();
		cnt = 0;

		for (j = 0; j < N; j++)
		{
			outSt = powArr[--SP];

			while (1)
			{
				if (outSt == Quepow[RPp])
				{
					outi = Popi();
					outp = Popp();
					cnt++;
					break;
				}

				Puship(Popi(), Popp());
			}

			if (outi == M)
			{
				printf("%d\n", cnt);
				break;
			}
		}
	}

	return 0;


}

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

문제

문제

출처

ICPC

프린터 큐 시간초과 질문드려요..

vvv3334 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말