[24/10/8]

1억번 연산 >> 1초의 시간 

 

연산횟수 = 알고리즘 시간복잡도 * 데이터의 크기

ex) 버블정렬이면 n^2이니까 데이터의 크기가 100만이면 (100만)^2 = 2초의 시간은 불가능함

2초의 시간 == 2억번 , (100만)^2 > 2억번이라서...

 

1) 시간제한보고 알맞는 알고리즘 선택기준

2)) 비효율적인 로직 찾아서 효율적으로 바꿀때

 

기본적으로 자료형 int가 아닌 long형으로 하는 습관을 들이자. int형은 21만밖에 안됨

 

ArrayList

배열: 간단하고 데이터 크기가 fix, 데이터 접근이 많을때도

리스트: 크기가 변하거나 , 데이터가 삽입 삭제가 많을때도

구간합

구간합

총 n번의 구간합을 구하기 위한 for문 하나 + 입력받는 배열을 뒤지면서 (for문 한번) 각각의 구간합을 구하면 총 O(n^2)인데 이보다 더 빨리 구하는 방법이 있음.

입력받으면서 for문 돌때 그때 바로 합 배열을 만들어버리면 O(n)임.

 

11659

 

//고친 풀이
import java.util.*;
import java.lang.*;
import java.io.*;
// O(n) 이하
// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int t= sc.nextInt();
        long[] arr = new long[l];
        long[] sumArray = new long[l];
        for(int i=0; i<l; i++){
            arr[i]=sc.nextLong();
            //합배열 저장
            if(i==0){
                sumArray[0]=arr[0];
            }
            else{
                sumArray[i]=arr[i]+sumArray[i-1];
            }
        } 
        for(int i=0; i<t; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            System.out.println(rangeSum(sumArray,start,end));
        }

        
    }
    //start번째부터 end까지의 구간합
    static long rangeSum(long[] sumArray,int start ,int end){
        if(start==1){
            return sumArray[end-1];
        }
        else{
            return sumArray[end-1]-sumArray[start-2];
        }
    }
}

기본적으로 O(n^2)으로 할려했는데 (100000)^2 하니까 1억번이 넘어가서 무지성으로 풀면 안됨.

구간합 배열을 이용하여 O(n)으로 줄여놔야함.

 

BufferedReader

Scanner 같은 경우는 자동으로 편의기능을 제공해주다보니 속도가 다소 느림

BufferedReader bufferedReader = 
new BufferedReader(new InputStreamReader(System.in));


//bufferedReader.readLine()으로 한줄씩 받아서 StringTokenizer을 이용하여 각각을 파싱하여
// 형변환 후 사용하면 됨.
StringTokenizer stringTokenizer =
new StringTokenizer(bufferedReader.readLine());

//줄을 받아서 직접 파싱하여 int로 바꿈
int suNo= Integer.parseInt(stringTokenizer.nextToken());
int quizNo= Integer.parseInt(stringTokenizer.nextToken());

stringTokenizer = new StringTokenizer(bufferedReader.readLine());

Integer.parseInt(stringTokenizer.nextToken());

 

S[i] = S[i-1] + (입력받는 값) 으로 원본 배열 저장 없이 바로 구간합 배열에 저장.

 

투포인터

포인터(가르키는 인덱스) 2개 잡고 그 2개 각각을 이동시키면서 시간복잡도 O(2n) 이 나오게 하는 방법임

초기 count가 1인건 자기 자신(15)일때 될 수 있는 합의 경우의 수는 기본적으로 자기 자신 한개는 보장하기 때문임.

그런데 굳이 배열 만들 필요도 없음. 그냥 start_index =1 , end_index=1로 잡아놓고 배열 없이 값 올리면서 사용하면 됨.

import java.util.*;
import java.lang.*;
import java.io.*;
// O(n) 으로 가야함
// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 1;
        int start_index = 1; 
        int end_index=1;
        int sum=1;
        while(end_index!=N){
            if(sum>N){
                sum-=start_index;
                start_index++;
            }
            else if(sum<N){
                end_index++;
                sum=sum+end_index;
            }
            else {
                count++;
                end_index++;
                sum=sum+end_index;
            }
        }
        System.out.println(count);
    }
}