구간 합 이론
-
합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] -
합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.
-
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i] -
구간 합을 구하는 공식
S[j] - S[i-1] -
합 배열과 구간 합 공식을 적재적소에 활용하면 코딩 테스트에서 시간복잡도를 줄이는 데 많은 도움이 될 것이다.
문제풀이 백준 11659번
<나의 풀이>
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int[] count = new int[2];
for(int i=0; i<2; i++){
count[i] = sc.nextInt();
}
int[] nums = new int[count[0]];
int[] sum = new int[count[0]];
for(int i=0; i<count[0]; i++){
nums[i] = sc.nextInt();
if (i == 0){
sum[i] = nums[i];
} else{
sum[i] = sum[i-1]+nums[i];
}
}
for (int i=0; i<count[1]; i++){
int[] n = new int[2];
for(int j=0; j<2; j++){
n[j] = sc.nextInt();
}
System.out.println(sum[n[1]-1]-sum[n[0]-1]+nums[n[0]-1]);
}
}
}<교재 풀이>
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader bufferedReader = new BufferedReader(new java.io.InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int suNo = Integer.valueOf(stringTokenizer.nextToken());
int quizNo = Integer.valueOf(stringTokenizer.nextToken());
long[] S = new long[suNo+1];
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i=1; i<= suNo; i++) {
S[i] = S[i-1] + Integer.valueOf(stringTokenizer.nextToken());
}
for (int q=0; q < quizNo; q++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int i = Integer.valueOf(stringTokenizer.nextToken());
int j = Integer.valueOf(stringTokenizer.nextToken());
System.out.println(S[j]-S[i-1]);
}
}
}
배운 내용
-
bufferedreader
- Scanner와 유사하다. 기존에 쓰던 Scanner보다 속도 측면에서 훨씬 빠르기 때문에(입력된 데이터가 바로 전달되지 않고 버퍼를 거쳐 전달되므로 데이터 처리 효율성을 높임) 많은 양의 데이터를 처리할 때 유리하다.
- Enter만 경계로 인식하고 받은 데이터는 String으로 고정되기 때문에 입력받은 데이터를 가공하는 작업이 필요한 경우가 많다.
- 예외처리를 반드시 필요로 한다. readLine()시 마다 try/catch문으로 감싸주어도 되고, throws IOException 을 통한 예외처리를 해도 된다.(대부분의 경우에 후자를 사용한다.)
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); //선언 String s = bf.readLine(); //String int i = Integer.parseInt(bf.readLine()); //Int ```
-
StringTokenizer
-
StringTokenizer 클래스는 문자열을 우리가 지정한 구분자로 문자열을 쪼개주는 클래스이다. 그렇게 쪼개어진 문자열을 우리는 토큰(token)이라고 부른다.
-
String Tokenizer st = new StringTokenizer(String str) 파싱 할 문자열을 인자로 받는다. 구분자를 지정하지 않았으므로 스페이스, 탭, 줄바꿈, 캐리지 리턴 등 기본 구분자가 적용된다. -
String Tokenizer st = new StringTokenizer(String str, String 구분자) 파싱할 문자열과 구분자를 인자로 받는다. -
String Tokenizer st = new StringTokenizer(String str, String 구분자, true/false) 파싱할 문자열과 구분자를 인자로 받는다. true/flase로 구분자 자체도 토큰으로 인식하게 할지 여부를 정한다. -
문자열 파싱으로 String의 split 메서드를 사용할 수도 있다.
String[] s = str.split(구분자)- StringTokenizer와의 차이점 : split은 빈문자열은 토큰으로 인식하지만 StringTokenizer는 빈 문자열을 토큰으로 인식하지 않는다.
-
-
예외 처리
- throws : 메소드를 정의할 때 사용하며, 이 메소드에서 발생할 수 있는 Exception을 명시적으로 정의할 때 사용한다. throws를 보면 잠재적으로 어떤 Exception을 발생될 수 있는지 알 수 있다.
- throw : Exception을 발생시킬 때 사용하는 키워드. 예상치 못한 일이 발생했을 때 Exception을 발생시켜 예외가 처리될 수 있도록 한다.
- 예시
public static int parseInt(String s, int radix) throws NumberFormatException { if (s == null) { throw new NumberFormatException("null"); } if (radix < Character.MIN_RADIX) { throw new NumberFormatException("radix " + radix + " less than Character.MIN_RADIX"); } .... }
문제풀이 백준 11660번
<나의 풀이1>
시간 초과가 떴다. 코드 후반에서 무려 삼중 for문을 사용했기 때문이다. (사실 예상했지만 그냥 돌려봤다..) 최적화를 해서 소요시간을 줄여보자..!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.valueOf(st.nextToken());
int m = Integer.valueOf(st.nextToken());
int[][] nums = new int[n+1][n+1];
for(int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=1; j<=n; j++) {
nums[i][j] = Integer.valueOf(st.nextToken());
}
}
for (int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.valueOf(st.nextToken());
int y1 = Integer.valueOf(st.nextToken());
int x2 = Integer.valueOf(st.nextToken());
int y2 = Integer.valueOf(st.nextToken());
int sum = 0;
for (int x=x1; x<=x2; x++) {
for(int y=y1; y<=y2; y++) {
sum += nums[x][y];
}
}
System.out.println(sum);
}
}
}그리고 천천히 생각해보니 제목부터 구간 합 이라고 적었으면서 구간 합 개념을 이용하지 않았다.. 다시 풀이를 해서 끔찍한 삼중 for문을 없앴고.. 결국은 맞았다 !
<나의 풀이2>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.valueOf(st.nextToken());
int m = Integer.valueOf(st.nextToken());
int[][] nums = new int[n+1][n+1];
int[][] sum = new int[n+1][n+1];
for(int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=1; j<=n; j++) {
nums[i][j] = Integer.valueOf(st.nextToken());
sum[i][j] = sum[i-1][j] + sum[i][j-1] + nums[i][j] - sum[i-1][j-1];
}
}
for (int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.valueOf(st.nextToken());
int y1 = Integer.valueOf(st.nextToken());
int x2 = Integer.valueOf(st.nextToken());
int y2 = Integer.valueOf(st.nextToken());
System.out.println(sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]);
}
}
}<교재 풀이>
package coding_test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
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[][] A = new int[N+1][N+1];
for(int i=1; i<=N; i++) {
st = new StringTokenizer(br.readLine());
for (int j=1; j<=N; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] D = new int[N+1][N+1];
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
D[i][j] = D[i-1][j] + D[i][j-1] - D[i-1][j-1] + A[i][j];
}
}
for (int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.valueOf(st.nextToken());
int y1 = Integer.valueOf(st.nextToken());
int x2 = Integer.valueOf(st.nextToken());
int y2 = Integer.valueOf(st.nextToken());
int result = D[x2][y2]-D[x2][y1-1]-D[x1-1][y2]+D[x1-1][y1-1];
System.out.println(result);
}
}
}
내 풀이와 매우 비슷하다.
배운 내용
- 주어진 시간을 보고 구간 합 개념을 이용해서 문제를 해결할 수 있다.
문제풀이 백준 10986번
문제를 풀지 못했다. 시도를 했으나 시간 초과가 되어 교재의 풀이법을 확인했다.
핵심 풀이법
(A+B)%C 는 ((A%C)+(B%C))%C 와 같다. 다시 말해 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
구간 합 배열을 S[i]라고 했을 때 S[i]%m 의 값과 S[j]%m의 값이 같다면 (S[i]-S[j])%M은 0이다.
즉 구간 합 배열의 원소를 m으로 나눈 나머지로 업데이트하고 S[i]와 S[j]가 같은 (i,j)쌍을 찾으면 원본 배열에서 j+1부터 i까지의 구간합이 m으로 나누어 떨어진다는 것을 알 수 있다.
<교재 풀이> (코드 길이를 줄이기 위해 약간 수정했다.)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.valueOf(st.nextToken());
int m = Integer.valueOf(st.nextToken());
long[] S = new long[n];
long[] C = new long[m];
long ans = 0;
st = new StringTokenizer(br.readLine());
S[0] = Integer.valueOf(st.nextToken());
C[(int) (S[0]%m)] ++;
for(int i=1; i<n; i++){
S[i] = S[i-1] + Integer.valueOf(st.nextToken());
int remainder = (int) (S[i]%m);
C[remainder] ++;
}
ans += C[0];
for (int i=0; i<m; i++){
if (C[i]>1){
ans += (C[i]*(C[i]-1)/2);
}
}
System.out.println(ans);
}
}배운 내용
- 배열 크기는 자료형 long으로 선언할 수 없다.
- 잘못된 예
long n = 10; long[] nums = new long[n]; - 나머지 연산 풀이법
권혁상입니다. 행복코딩^_^