글 읽기 - 반례를 알고 싶습니다.

adfsfsf 4년 전 0

아주 기본적인 아이디어로 적었습니다. 구체적인 내용은 주석을 참고해주시길 바랍니다. 이해가 안 되시는 부분은 적어주시면 수정하겠습니다.

#include <stdio.h>
#include <stdlib.h>
struct numbers {
	long long int num, index;
};
int main(void)
{
	struct numbers nums[1000005];
	long long int i, j, k, indexs[1000005], indexs2[1000005], indexNum = 0, n;
	short check = 0;
	scanf("%lld", &n);
	for (i = 0; i < n; i++)//n개의 수에 대하여
	{
		scanf("%lld", &nums[i].num);//수를 입력받는다.
		nums[i].index = i;//입력받은 수의 오큰수의 인덱스를 자기자신의 위치로 한다.
		if (i == 0)//첫 수이면
        {
			indexs[0] = 0;//오큰수를 구하지 못한 수의 인덱스 배열의 첫 값으로 0을 넣는다.
			indexNum = 1;//오큰수를 구하지 못한 수의 개수를 1로 놓는다.
		}
		else if (check == 0)//check가 0이면 오큰수를 구하지 못한 수의 인덱스의 배열은 indexs이다.
		{
			k = 0;
			for (j = 0; j < indexNum; j++)//오큰수를 구하지 못한 수들의 인덱스에 대해
			{
				if (nums[indexs[j]].num < nums[i].num)//만약 현재 조사 중인 인덱스의 수가 이번에 입력받은 수보다 작다면
				{
					nums[indexs[j]].index = i;//해당하는 수의 오큰수를 현재 수로 바꾼다.
				}
				else
				{
					indexs2[k] = indexs[j];//아니라면 새로운 배열로 현재 조사 중인 인덱스를 그대로 넣는다.
					k++;
				}
			}
			indexs2[k] = i;
			indexNum = k + 1;
			check = 1;
		}
		else//check가 1이면 오큰수를 구하지 못한 수의 인덱스의 배열은 indexs2이다. check가 0인 경우와 저장위치만 반대고 나머지는 동일하다.
		{
			k = 0;
			for (j = 0; j < indexNum; j++)
			{
				if (nums[indexs2[j]].num < nums[i].num)
				{
					nums[indexs2[j]].index = i;
				}
				else
				{
					indexs[k] = indexs2[j];
					k++;
				}
			}
			indexs[k] = i;
			indexNum = k + 1;
			check = 0;
		}
	}
	for (i = 0; i < n; i++)//입력받은 모든 수에 대해
	{
		if (nums[i].index != i)//자기자신을 가리키고 있지 않으면 가리키는 수를 오큰수로써 출력한다.
			printf("%lld ", nums[nums[i].index].num);
		else//이외에는 -1을 출력한다.
			printf("-1 ");
	}
	return 0;
}

adfsfsf 4년 전 0

실험 결과, 마지막에 줄바꿈을 삽입하지 않으면 틀린 것으로 처리됩니다. 또한, 마지막 수를 출력한 후에는 빈 칸을 출력하면 안 됩니다.

문제는 위 코드는 시간초과가 일어난다는 점입니다.

urimaj 4년 전 0

N 이 1,000,000까지 될 수 있기 때문에 O(N^2) 솔루션은 시간 초과가 뜰 거 같습니다. 스택을 이용해서 O(N) 솔루션을 구현하면 될 듯 합니다.

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

문제

문제

출처

ICPC

반례를 알고 싶습니다.

adfsfsf 4년 전 0

adfsfsf 4년 전 0

urimaj 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말