글 읽기 - 시간초과 질문

dnstjr4567 1년 전 0

시간초과가 나는 이유가 뭔지 궁금합니다.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;

namespace 백준
{
    class MainApp
    {
        static void Main()
        {
            StringBuilder sb = new StringBuilder();
            int n = int.Parse(ReadLine());
            List<int> nums = new List<int>();
            
            int mod = 0;
            
            int cntmax = 0;
            for (int i = 0; i < n; i++)
            {
                int cnt = 1;
                int x = int.Parse(ReadLine());
                nums.Add(x);
                nums.Sort();
                if (nums.Contains(x)) 
                {
                    cnt++;
                    if (cnt > cntmax) { cntmax = cnt; mod = x; }
                }
                
            }
            sb.Append(Convert.ToInt32(nums.Average())+" ");
            sb.Append( nums[nums.Count / 2]+" ");
            sb.Append(mod+" ");
            sb.Append( nums.Max() - nums.Min());
            WriteLine(sb.ToString());
           
        }
    }
}

nahwasa 1년 전 1

nums.Sort();

매번 정렬이 필요할지 한번 생각해보세요.

현재 입력받으면서 정렬하는부분만 해도 O(N^2logN) 입니다.

dnstjr4567 1년 전 0

시간초과는 해결된 것 같은데 계속 틀렸다고 나오네요ㅜㅜ 질문검색에서 나온 반례들도 다 맞는 것 같은데 다른 반례 있을까요?

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Console;

namespace 백준
{
    class MainApp
    {
        static void Main()
        {
            StringBuilder sb = new StringBuilder();
            int n = int.Parse(ReadLine());
            List<int> nums = new List<int>();
            List<int> mod = new List<int>();
            

            int cntmax = 0;
            for (int i = 0; i < n; i++)
            {
                int cnt = 1;
                int x = int.Parse(ReadLine());
                nums.Add(x);
                
                if (nums.Contains(x))
                {
                    cnt++;
                    if (cnt >= cntmax) { cntmax = cnt; mod.Add(x) ; }
                    
                }

            }nums.Sort();mod.Sort();
            sb.Append(Convert.ToInt32(nums.Average()) + " ");
            sb.Append(nums[nums.Count / 2] + " ");
            if (mod.Count == 1)
            { sb.Append(mod[0] + " "); }
            else { sb.Append(mod[1] + " "); }
            sb.Append(nums.Max() - nums.Min());
            WriteLine(sb.ToString());

        }
    }
}

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

문제

문제

출처

ICPC

시간초과 질문

dnstjr4567 1년 전 0

nahwasa 1년 전 1

dnstjr4567 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말