글 읽기 - 이상합니다

dnstjr4567 1년 전 0

N이 1500넘어가면 작동이 안되는 이유가 뭘까요?

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()
        {
            int n = int.Parse(ReadLine());
            List<long>nums = new List<long>(Array.ConvertAll(ReadLine().Split(), long.Parse));
            int cnt = 0;
            int i = 0;
            while(i!=nums.Count)
            {
                
                if (nums[i] != i + 1) { nums.RemoveAt(i); cnt++;nums = new List<long>(nums);if (nums.Count == 0) { break; } }
                
                else { i++; }
                
                
            }
            WriteLine(cnt);

        }
    }
}

wnwoghd22 1년 전 1

시간을 줄여야겠습니다.

nums에 다시 List를 할당해 넣는 것은 불필요합니다.

RemoveAt 메소드를 실행시키면 뒤에 있는 모든 원소들을 한칸씩 당기기 때문에 시간복잡도는 O(n)입니다. 원소 하나 삭제하는 것 치고는 비용이 비싸죠.

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

문제

문제

출처

ICPC

이상합니다

dnstjr4567 1년 전 0

wnwoghd22 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말