PKU 1089. Intervals. [판정:WA]

Milkskin 2009. 5. 21. 15:15

위의 3건이 가장 최근에 제출해본 것입니다

그중 첫번째(Run ID: 5178307)는 검토해보니 정말 틀린부분이 있어서 WA가 났고

두번째(Run ID: 5192652)는 검토해보니 최악의 경우 O(n²)까지도 나올지도 모르겠더군요
(무작정 입력을 받아서 전부 정렬한 뒤에 겹치는 부분을 출력에서 생략하는 방식이라 -_-;)

그래서 팀블로그에 가장 마지막으로 끄적인 Intervals 풀이의 알고리즘과 유사하게 풀어보았습니다만
왜 WA가 또-_- 나오는지는 모르겠네요

#include <iostream>
using namespace std;

class Interval
{
public:
	int lower;
	int upper;

Interval() { lower = 0, upper = 0; }
	Interval( int a, int b ) { lower = a, upper = b; }
};

class Queue
{
public:
	Interval *list; // circular array
	int size;
	int exist;
	int front;
	int back;

Queue() { size = 0, exist = 0, front = 0, back = 0, list = NULL; }
	Queue( int n ) { size = n, exist = 0, front = 0, back = 0, list = new Interval[n]; }

void push( Interval in )
	{
		list[back % size] = in;
		back = ++back % (size * 2);
		exist++;
	}
	Interval pop()
	{
		Interval oldvalue;

oldvalue = list[front % size];
		front = ++front % (size * 2);
		exist--;

return oldvalue;
	}
};

int main()
{
	int n;
	int i, j, k;
	int actual; // revised index

scanf("%d", &n);

Queue q(n);

// input intervals
	for( i = 0; i < n; i++ )
	{
		Interval receive;

scanf("%d %d", &receive.lower, &receive.upper);

for( j = 0; j < q.exist; j++ )
		{
			int diff1, diff2;

actual = (j + q.front) % q.size;

diff1 = q.list[actual].upper - receive.lower;
			diff2 = q.list[actual].lower - receive.upper;

if( diff1 > 0 ) diff1 = !!diff1; // become sign: prevent overflow
			if( diff2 > 0 ) diff2 = !!diff2; // same intention

if( diff1 * diff2 <= 0 ) // intersection is exist
			{
				Interval temp;

k = 0;
				for( ; k < j; k++ )
				{
					temp = q.pop();
					q.push(temp);
				}

if( k != 0 ) j -= k;
				else
				{
					temp = q.pop();

if( receive.lower > temp.lower ) receive.lower = temp.lower;
					if( receive.upper < temp.upper ) receive.upper = temp.upper;
				}

j--; // repeat
			}
		}

q.push(receive);
	}

// sort intervals: selection sort
	int min, minindex;

for( i = 0; i < q.exist - 1; i++ )
	{
		actual = (i + q.front) % q.size;

min = q.list[actual].lower;
		minindex = actual;
		
		for( j = i; j < q.exist; j++ )
		{
			k = (j + q.front) % q.size;

if( min > q.list[k].lower )
			{
				min = q.list[k].lower;
				minindex = k;
			}
		}

if( minindex != actual )
		{
			swap( q.list[actual].lower, q.list[minindex].lower );
			swap( q.list[actual].upper, q.list[minindex].upper );
		}
	}

// print intervals
	for( i = 0; i < q.exist; i++ )
	{
		actual = (i + q.front) % q.size;

printf("%d %d\n", q.list[actual].lower, q.list[actual].upper);
	}

return 0;
}

지난번에 올려놓은 풀이는 리스트를 직접 만들어서 사용했지만
linked list방식이 다소 불안정한 면이 있는 것 같아서

이번에는 환형 배열을 사용한 큐를 택했는데 -_-;

뭔가 특수한 케이스가 있어서 그른지
아니면 소스가 잘못된건지 ㅠ