글 읽기 - 개선된 버블정렬로 하여도 시간초과가 뜨는데요;;;

yeop9657 8년 전 0

이거 버블정렬 말고 다른 정렬 써야하는 문제인가요?

#include <cstdio>
#define SIZE 500001
#define SWAP(X, Y, Z) (Z=X); (X=Y); (Y=Z);

int arr[SIZE];

int main(void)
{
	/* Input */
	long long num1 = 0, num2 = 0, temp = 0;
	bool bCheck = true;
	scanf("%d", &num1);

	for (int ii = 0; ii < num1; ii++) { scanf("%d", &arr[ii]); }

	for (int ii = 0; bCheck; ii++)
	{
		bCheck = false;
		for (int jj = 0; jj < num1 - (ii + 1); jj++)
		{
			if (arr[jj] > arr[jj + 1]) { SWAP(arr[jj], arr[jj + 1], temp); bCheck = true; num2++; }
		}
	}

	/* Output */
	printf("%d\n", num2);

	return 0;
}

pl0892029 8년 전 0

합병 정렬을 이용해서 O(NlogN) 혹은 인덱스트리를 이용해서 O(NlogN)에 가능합니다.

yeop9657 8년 전 0

버블정렬문제인데 합병 정렬 사용해도 되나요?

pl0892029 8년 전 0

이 문제에서 원하는건 진짜로 버블정렬을 쓰라는게 아닙니다.

버블 정렬로 했을 때 몇번의 교환 연산이 있는지를 물어보는 문제입니다.

따라서 교환 연산의 수를 정확히 셀 수 있다면 버블정렬이거나 합병정렬을 써도 문제가 없습니다. :)

(그리고 합병 정렬을 쓰면 그냥 되는게 아니라, 잘 써야 됩니다. ㅎㅎ)

yukariko 8년 전 0

저는 정렬 + 이진탐색으로 해결했습니다.

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

문제

문제

출처

ICPC

개선된 버블정렬로 하여도 시간초과가 뜨는데요;;;

yeop9657 8년 전 0

pl0892029 8년 전 0

yeop9657 8년 전 0

pl0892029 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말