글 읽기 - 왜 오답인지 모르겠네요..

junimnjw 6년 전 0

TC 에서 제대로 나오는 것 같고 문제가 없어보이는데 계속 틀렸다고 나오네요.. 혹시 어디가 문제일까요?

단순히 Heap Sort 만 사용해서는 안되는건가요?

고수님 도움 부탁드립니다.

#include <stdio.h>

typedef struct Doc
{
	int id;
	int priority;
}Doc;

Doc queue[100];
int rear;


void QueueInit()
{
	for (int i = 0; i < 100; i++)
	{
		queue[i].id = 0;
		queue[i].priority = 0;
	}

	//Start from 1
	rear = 1;
}

void QueuePush(Doc x)
{
	queue[rear].id = x.id;
	queue[rear].priority = x.priority;
	
	//Heapifiy
	int curIdx = rear;
	int parIdx;
	while (queue[parIdx = curIdx / 2].priority < queue[curIdx].priority  && parIdx > 0)
	{
		Doc temp;
		temp.id = queue[curIdx].id;
		temp.priority = queue[curIdx].priority;

		queue[curIdx].id = queue[parIdx].id;
		queue[curIdx].priority = queue[parIdx].priority;

		queue[parIdx].id = temp.id;
		queue[parIdx].priority = temp.priority;
		
		curIdx = parIdx;
	}

	rear++;
}

int QueueSize()
{
	return (rear - 1);
}

Doc QueuePop()
{	
	Doc ret;

	ret = queue[1];	
	queue[1] = queue[rear - 1];
	queue[rear - 1].id = 0;
	queue[rear - 1].priority = 0;
	rear--;

	int curIdx, leftIdx, rightIdx;
	curIdx = 1;
	int nodeChanged = 1;
	while (nodeChanged)
	{
		leftIdx = 2 * curIdx;
		rightIdx = 2 * curIdx + 1;
		nodeChanged = 0;
		if (queue[leftIdx].priority > queue[curIdx].priority && (leftIdx < rear))
		{
			Doc temp = queue[curIdx];
			queue[curIdx] = queue[leftIdx];
			queue[leftIdx] = temp;
			nodeChanged = 1;
			curIdx = leftIdx;
			continue;
		}

		if (queue[rightIdx].priority > queue[curIdx].priority && (rightIdx < rear))
		{
			Doc temp = queue[curIdx];
			queue[curIdx] = queue[rightIdx];
			queue[rightIdx] = temp;
			nodeChanged = 1;
			curIdx = rightIdx;
			nodeChanged = 1;
			continue;
		}
	}
	
	return ret;
}

int main()
{
	freopen("input.txt", "r", stdin);

	int T;
	scanf("%d", &T);
	for (int tc = 0; tc < T; tc++)
	{	
		QueueInit();
				
		int num, find;
		scanf("%d%d", &num, &find);

		for (int n = 0; n < num; n++)
		{
			Doc temp;
			int prioity;
			scanf("%d", &prioity);
			temp.id = n;
			temp.priority = prioity;
			QueuePush(temp);			
		}

		
		for (int n = 1; n <= num; n++)
		{
			Doc temp = QueuePop();			
			if (temp.id == find)
			{
				printf("%d\n", n);
			}
		}
	}
}

chogahui05 6년 전 0

네.

Heap sort는 안정 정렬이 아닙니닷! Heap sorting 하실 때 proirity만 기준으로 위로 올리고 내리고 하신 거 같은데.

당연히 같은 우선순위라면 Top에 누가 먼저 올라오느냐에 따라서 순서가 달라지기 때문에

안정 정렬이 아니에요. 자세한 정보는 여기 봅시다~

https://stackoverflow.com/ques...

chogahui05 6년 전 2

의외로 빈도 정렬 같은 문제에서

테케는 맞는 데 왜 틀리나요? 라는 질문이 심심찮게 들어오는데요.

들어온 순서에 따라서. 그리고 정렬 후에도 우선순위가 같을 때, 상대적인 순서가 같은 게 보장된다.

그러니까 stable하게 정렬이 된다면, 들어온 순서를 sort의 기준으로 안 써도 됩니다.

But. 그렇지 않은 경우 (ex. selection sort)

들어온 순서에 상관없이, 우선순위만 같다면 순서가 뒤바뀌어버릴수도 있기 때문에

들어온 순서에 따라 정렬을 해야 한다.

그러면 기준을 '들어온 순서' 하나 더 추가해야 합니다.

Question.

c++의 stable_sort와 sort는 내부적으로 어떤 알고리듬으로 구현이 되어 있을까요?

이것도 알아보시면 좋을 거 같습니다.

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

문제

문제

출처

ICPC

왜 오답인지 모르겠네요..

junimnjw 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말