글 읽기 - 스택 안쓰고 O(N)으로 풀었는데 왜 시간초과가 뜰까요 ㅜㅜ

sky0331 5년 전 0

스택으로 풀어도 O(N) 아닌가용??

답은 잘 나오는 것 같은데..

#include <stdio.h>
int n, maxi, a[1000001], b[1000001], x;
int main(void)
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	maxi = a[n];
	for (int i = n; i >= 1; i--)
	{
		if (a[i] > maxi)
		{
			b[i] = 1;
			maxi = a[i];
		}
	}
	x = 0;
	for (int i = 1; i <= n; i++)
	{
		a[i] = x;
		if (b[i])
			x = i;
		printf("%d ", a[i]);
	}
}

djm03178 5년 전 0

이 문제에서 시간 초과를 받으신 제출이 딱 하나신데, 길이가 1909바이트나 됩니다. 이 코드는 아무리 봐도 그렇게 길지 않네요.

sky0331 5년 전 0

아 제출한 1909바이트 짜리 코드는 앞에 불필요한(사용하지 않는) 변수/함수들이 많아서 핵심 부분만 올린 거에요!

지금 코드는 시간 초과가 날 부분이 없습니다. 핵심 부분만 올리셨다고 했는데, 코드는 웬만하면 항상 전체를 올려야 합니다. 불필요하다고 생각하신 부분이 실제로 프로그램에 미치는 영향이 어떨지 100% 확신하실 수 있나요? 코드에서 단 한 글자라도 달라지면 전혀 다른 결과를 얻을 수 있는 것이 프로그래밍 언어입니다. 이 코드 그대로 제출해 보면 시간 초과가 안 나고 틀렸습니다가 나오는 것만 봐도 그렇죠.

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

문제

문제

출처

ICPC

스택 안쓰고 O(N)으로 풀었는데 왜 시간초과가 뜰까요 ㅜㅜ

sky0331 5년 전 0

ho94949 5년 전 0

sky0331 5년 전 0

3587jjh 5년 전 0

indioindio 5년 전 0

djm03178 5년 전 0

sky0331 5년 전 0

indioindio 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말