🤔구간 합 알고리즘
왜 필요 한가?
for(int i=0; i<배열의 크기; i++){
arr[i] = scanner.nextInt();
}
/* 인덱스0부터 n-1 까지의 합을 구하라
시간 복잡도 O(N) */
해당 합을 시간 복잡도 O(1)로 구할 수 있는 방법
➡️ 구간 합 알고리즘
배열 arr을 입력 받기 전에 구간 합을 저장 할 배열 S를 생성해주고
배열 arr에 정수를 입력할때 배열 S에도 입력
S[0] = arr[0]
S[1] = S[0] + arr[1]
. . . . . .
S[i] = S[i-1] + arr[i];
이렇게 배열에 대한 합들을 기록.
Ex)
arr = [15,13,10,7,3,12]
S = [15,28,38,45,48,60]
배열 arr의 인덱스 2부터 4까지의 합을 구해라.
10 + 7 + 3 = 20 O(N)
arr[2] + arr[3] + arr[4]
배열 S를 통한 정답 구하기
S[4] - S[1] = 20 O(1)
인덱스 4까지의 합 - 인덱스 1까지의 합 = 인덱스 2~ 4까지의 합
🔍배열 구간에 대한 합을 구하는데 유용하다.
❔[Silver3] 구간 합 구하기
📢 WARNING!!!
지금 합을 구해야 하는 횟수가 100,000개 나 된다. Scanner로 입력 받으면 시간제한으로 인해 백준에서 돌아가지 않는다.이때, BufferedReader를 사용 해야 한다.
BufferedReader가 Scanner를 사용 하는 것보다 빠르고, 문자열에 최적화 돼있기 때문.
BufferedReader
import java.io.BufferedReader;
import java.io.InputStreamReader;
1 2 3 4 5 6 7 8 9 10 11 12 // 한줄 입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
// s[0] = "1"; Integer.parseInt(s[0]) => 1
// s[1] = "2";
// s[2] = "3";
// .....StringTokenizer을 활용 해준다
StringTokenizer 사용목적
- BufferedReader는 잘라서 배열과 같이 인덱스를 사용하여 접근하여 사용.
- StringTokenizer는 공백이 있다면 뒤에 문자열이 공백 자리를 땡겨 채우도록 한다.
- StringTokenizer가 BufferedReader보다 빠르게 사용될 수 있다.
- 문자열을 자르게 위해 split을 사용할땐, split은 정규식을 기반으로 자르는 로직으로서 내부는 복잡하다. 그에 비해 StringTokenizer의 nextToken()메소드는 단순히 공백 자리를 땡겨 채우는 것이다. 그렇기 때문에 속도 차이가 날 수 밖에 없다.
- 정규식이나 인덱스 접근과 같은 처리가 필요없다면 StringTokenizer를 사용하는 것이 효율적이다.
StringTokenizer 사용법
- 자바에서는 String을 token단위로 끊어주는 StringTokenizer 클래스를 제공한다.
- 예를들어 “this is my string” 이라는 스트링을 this, is, my, string 4개의 스트링으로 끊어주는 기능을 제공한다.
- 그리고 공백말고도 다른 구획문자(delimiter)를 사용할수도 있다.
- 예를들어 this%is%my%string을 delimiter에 %를 넣어 StringTokenizer를 사용하면 마찬가지로 this, is, my, string으로 읽어준다.
- thismy%string^일때 구획문자를 “$%^”라고 설정해주면 this, is, my, string 으로 끊어준다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in);
StringTokenizer st = new StringTokenizer(br.readLine());
// AB CDD EFFF GH 입력
st.nextToken() // AB
st.nextToken() // CDD
st.nextToken() // EFFF
st.nextToken() // GH⚙️ CODE
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class App2{
/*
br.readLine() 같이 파일처리 등 입출력 관련된 코드를 사용할땐
IOException 예외처리를 해줘야 한다.
*/
public static void main(String[] args) throws IOException{
//M이 100,000개 하면 그 안에서 System.out.println을 100,000개 불러야 하기 때문에
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//수의 갯수
int N = Integer.parseInt(st.nextToken());
//합을 구해야 하는 횟수
int M = Integer.parseInt(st.nextToken());
/*
배열입력
int[] arr = new int[N];
*/
//구간 합 배열 (인덱스 1부터 시작)
int[] S = new int[N+1];
st = new StringTokenizer(br.readLine());
for(int i=1; i <= N; i++){
S[i] = S[i-1] + Integer.parseInt(st.nextToken());
}
//구간 합 출력
int left_th, right_th;
for(int i=0; i < M; i++){
st = new StringTokenizer(br.readLine());
left_th = Integer.parseInt(st.nextToken());
right_th = Integer.parseInt(st.nextToken());
sb.append(S[right_th] - S[left_th-1] + "\n");
}
System.out.println(sb);
}
}Int 배열을 생성할때 초기화를 0으로 해준다는 굉장히 사소한 부분이 중요하다.
➡️ S[i] - S[i-1] 이 오류없이 잘 흘러가게 되는 이유
❔[Silver1] 구간 합 구하기
2차원 배열 구간 합 구하기
이 또한 주어진 배열 사이즈 N 크기보다 +1 큰 배열을 선언해주고
초기화가 저절로 0이 된다는 성질을 이용해서 푸는게 포인트다.
⚙️ CODE
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int Dsum(int[][] D, int x1, int y1, int x2, int y2){
return ( D[x2][y2] - D[x2][y1-1] - D[x1-1][y2] + D[x1-1][y1-1]);
}
public static void main (String[] args) throws IOException{
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
//표의 크기
int N = Integer.parseInt(st.nextToken());
//합을 구해야 하는 횟수 M
int M = Integer.parseInt(st.nextToken());
//구간 합 2차원 배열
int[][] D = new int[N+1][N+1];
for(int i=1; i<N+1; i++){
st = new StringTokenizer(br.readLine());
for(int j=1; j<N+1; j++){
//구간합에서 배열+1 크기로 선언하면 굉장히 편해짐
D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + Integer.parseInt(st.nextToken());
}
}
for(int i=0; i<M; i++){
st = new StringTokenizer(br.readLine());
sb.append(Dsum(D, Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())) + "\n");
}
System.out.println(sb);
}
}
Game Developer