글 읽기 - 시간초과가 나는데 혹시 List.Sort()가 문제일까요?

wjddn7118 2년 전 0

계속 시간초과가 납니다.

★☆★☆★ [필독] 스택 수열 FAQ ★☆★☆★

에서 보니까 스택이나, List를 전부 순회하거나 하면 O(n^2)이 돼서 안 된다고 하던데 혹시 제 코드 중에서 List.Sort()가 리스트를 순회해서 시간초과가 나는 걸까요?

using System;
using static System.Console;
using System.Collections;
using System.Collections.Generic;
using System.Text;

public class main
{
    static public void Main()
	{
		int numRange = Convert.ToInt32(ReadLine());
		
		StringBuilder strBuilder = new StringBuilder();
		Stack<int> stack = new Stack<int>();
		bool wrong = false;
		int maxNum = 0;
		List<int> list = new List<int>();
		for(int i = 0; i < numRange; i++)
		{
			int num = Convert.ToInt32(ReadLine());
			
			if(stack.Count == 0)
			{
				for(int j = maxNum+1; j <= num; j++)
				{
					stack.Push(j);
					strBuilder.Append("+\n");
				}
			}
			else
			{
				if(num < stack.Peek())
				{
					wrong = true;
					break;
				}
				else if(num > stack.Peek())
				{
					for(int j = maxNum+1; j <= num; j++)
					{
						stack.Push(j);
						strBuilder.Append("+\n");
					}
				}
			}
			list.Add(stack.Peek());
			stack.Pop();
			strBuilder.Append("-\n");
			list.Sort();
			maxNum = list[list.Count-1];
		}
		if(wrong == true)
			WriteLine("NO");
		else
			WriteLine(strBuilder.ToString());
	}
}

bupjae 2년 전 1

list.Sort() 는 O(n log n) 함수입니다. 이 프로그램 전체의 시간복잡도는 O(n^2 log n) 이 됩니다.

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

문제

문제

출처

ICPC

시간초과가 나는데 혹시 List.Sort()가 문제일까요?

wjddn7118 2년 전 0

★☆★☆★ [필독] 스택 수열 FAQ ★☆★☆★

bupjae 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말