글 읽기 - 음주코딩 시간 초과 뜨는 이유를 모르겠습니다.

hj_d 9년 전 0

제 소스가 저런데 시간 초과가 뜨는데 이유를 모르겠습니다 ㅜㅜ

종료를 안해서 그런건가요??

import java.util.ArrayList;
import java.util.Scanner;
 
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Drink drink = new Drink();
        drink.start();
    }
 
}
 
class Drink
{
    Scanner sc = new Scanner(System.in);
     
    public void start()
    {
        while(sc.hasNext())
        {
            ArrayList <Integer> outPut =new ArrayList <Integer>();
            int n = sc.nextInt();
            int k = sc.nextInt();
            int array[] = new int [n];
            for(int i=0; i<n; i++)
            {
                array[i] = sc.nextInt(); 
            }
            for(int j=0; j<k; j++)
            {
                String m = sc.next();
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                if(m.equals("C"))
                {
                    array[n1-1]=n2;
                }
                else
                {
                    int sum = 1;
                    for(; n1<n2+1; n1++)
                    {
                        sum = sum*array[n1-1];
                    }
                    outPut.add(sum);
                }               
            }
            for(int i = 0; i<outPut.size(); i++)
            {
                if(outPut.get(i)>0)
                {
                    System.out.print("+");
                }
                else if(outPut.get(i)==0)
                {
                    System.out.print(0);
                }
                else
                {
                    System.out.print("-");
                }
                if(i==outPut.size()-1)
                {
                    System.out.println("");
                }
            }
 
        }
    }
}

portableangel 9년 전 1

위 소스는 K개의 각 쿼리당 O(N)의 시간복잡도로 결과를 구하기 때문에

시간복잡도가 O(N*K)로 N이 10만, K가 10만이니 시간 내에 돌릴 수가 없습니다.

저는 인덱스 트리를 이용해 각 쿼리를 O(logN)에 처리하는 방식을 사용하였습니다.

hj_d 9년 전 0

감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

음주코딩 시간 초과 뜨는 이유를 모르겠습니다.

hj_d 9년 전 0

portableangel 9년 전 1

hj_d 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말