글 읽기 - 시간초과의 이유를 모르겠습니다.

kocha24 5년 전 0

컴파일도 잘 되고 예제도 잘 출력됩니다.

시간초과의 이유를 모르겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE	1
#define FALSE	0

typedef struct _document {
	int value;
	int inputIndex;
}Document;

typedef Document Data;

typedef struct _node {
	Data data;
	struct _node *next;
} Node;

typedef struct _lQueue {
	Node *front;
	Node *rear;
} LQueue;

typedef LQueue Queue;

void queueInit(Queue *pqueue);
void pushX(Queue *pqueue, Data data);
Data pop(Queue *pqueue);
int size(Queue *pqueue);
int empty(Queue *pqueue);
Data front(Queue *pqueue);
Data back(Queue *pqueue);

void SequencePrinted(Queue *pqueue);
void Sort(Queue *pqueue, Data *documentList);

int count = 0;

int main(void) {
	int testCase = 0;
	Queue queue;

	queueInit(&queue);
	scanf("%d", &testCase);

	for (int i = 0; i < testCase; i++) {
		SequencePrinted(&queue);
	}

	return 0;
}
void queueInit(Queue *pqueue) {
	pqueue->front = NULL;
	pqueue->rear = NULL;
}
void pushX(Queue *pqueue, Data data) {
	Node *newNode = (Node*)malloc(sizeof(Node));

	newNode->next = NULL;
	newNode->data = data;

	if (empty(pqueue)) {
		pqueue->front = newNode;
		pqueue->rear = newNode;
	}
	else {
		pqueue->rear->next = newNode;
		pqueue->rear = newNode;
	}

	count++;
}

Data pop(Queue *pqueue) {
	Node *rnode;
	Data rdata;
	Document temp;
	temp.inputIndex = -1;
	temp.value = -1;

	if (empty(pqueue)) {
		return temp;
	}
	rnode = pqueue->front;
	rdata = rnode->data;
	pqueue->front = pqueue->front->next;

	free(rnode);

	count--;
	return rdata;
}

int size(Queue *pqueue) {
	return count;
}
int empty(Queue *pqueue) {
	if (pqueue->front == NULL)
		return TRUE;
	else
		return FALSE;
}
Data front(Queue *pqueue) {
	Document temp;
	temp.inputIndex = -1;
	temp.value = -1;

	if (empty(pqueue)) {
		return temp;
	}
	return pqueue->front->data;
}

Data back(Queue *pqueue) {
	Document temp;
	temp.inputIndex = -1;
	temp.value = -1;

	if (empty(pqueue)) {
		return temp;
	}
	return pqueue->rear->data;
}

void SequencePrinted(Queue *pqueue) {
	int numOfDocuments;
	int position;

	int targetValue = 0;
	int targetIndex = 0;
	int temp;
	Data dataTemp;

	scanf("%d %d", &numOfDocuments, &position);
	Data *priority = (Data*)malloc(sizeof(Data) * 100);

	for (int i = 0; i < numOfDocuments; i++) {
		scanf("%d", &temp);
		if (position == i) {
			targetValue = temp;
			targetIndex = i;
		}
		priority[i].value = temp;
		priority[i].inputIndex = i;
		pushX(pqueue, priority[i]);
	}
	Sort(pqueue, priority);

	int count = 0;
	while (1) {
		if (front(pqueue).value < priority[count].value) {
			dataTemp = pop(pqueue);
			pushX(pqueue, dataTemp);
		}
		else {
			if (front(pqueue).value == targetValue) {
				if (front(pqueue).inputIndex == targetIndex)
					break;
				else {
					pop(pqueue);
					count++;
				}
			}
			else if (front(pqueue).value == priority[count].value) {
				pop(pqueue);
				count++;
			}
		}
	}
	printf("%d\n", count + 1);
	free(priority);

	queueInit(pqueue);
}

void Sort(Queue *pqueue, Data *documentList) {
	int valueTemp;
	int indexTemp;
	for (int i = 0; i < size(pqueue); i++) {
		for (int j = 0; j < size(pqueue) - i - 1; j++) {
			if (documentList[j].value < documentList[j + 1].value) {
				valueTemp = documentList[j].value;
				indexTemp = documentList[j].inputIndex;
				documentList[j].value = documentList[j + 1].value;
				documentList[j].inputIndex = documentList[j + 1].inputIndex;
				documentList[j + 1].value = valueTemp;
				documentList[j + 1].inputIndex = indexTemp;
			}
		}
	}
}

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

문제

문제

출처

ICPC

시간초과의 이유를 모르겠습니다.

kocha24 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말