[백준11660]구간 합 구하기2

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

 

 

문제가 주어질 때마다 계산을 하면.. 시간이 초과되고

구간합을 구한 상태에서.. 계산해야 한다........

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class backjoon11660_2 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer stz = new StringTokenizer(br.readLine());
//		int N = Integer.parseInt(stz.nextToken());
//		int M = Integer.parseInt(stz.nextToken());
		String[] NM = br.readLine().split(" ");
		int N = Integer.parseInt(NM[0]);
		int M = Integer.parseInt(NM[1]);
//		System.out.println("N : "+N+" M:"+M);
		
		int[][] arr = new int[N+1][N+1];
		int[][] arrSum = new int[N+1][N+1];
		
		//2차원 배열 생성
		for(int i=0; i < N; i++) {//n이 4일 때 4번 돈다.1,2,3,4
			String newLine = br.readLine();
			String[] newLineArr = newLine.split(" ");
			for(int j=0; j < N; j++) {
				arr[i+1][j+1] = Integer.parseInt(newLineArr[j]);
			}	
		}
		
		//2차원 배열 출력
//		for(int i=0; i < arr.length; i++) {
//			System.out.println(Arrays.toString(arr[i]));
//		}
//		System.out.println("******************************");

		//2차원 배열의 구간합 생성
		for(int i=1; i < N+1; i++) {
			for(int j=1; j < N+1; j++) {//여기 중요..
				if(i == 1) {
					arrSum[1][j] = arrSum[1][j-1] + arr[1][j]; 
				}else if(j == 1) {
					arrSum[i][1] = arrSum[i-1][1] + arr[i][1];
				}else {
					arrSum[i][j] = arrSum[i][j-1] + arrSum[i-1][j] - arrSum[i-1][j-1] + arr[i][j];
				}
				
			}	
		}
		
		//2차원 구간 합 배열 출력
//		for(int i=0; i < arrSum.length; i++) {
//			System.out.println(Arrays.toString(arrSum[i]));
//		}
//		System.out.println("******************************");
		
		for(int i=0; i < M; i++) {
			String newLine = br.readLine();
			String[] newLineArr = newLine.split(" ");
			int x1 = Integer.parseInt(newLineArr[0]);
			int y1 = Integer.parseInt(newLineArr[1]);
			int x2 = Integer.parseInt(newLineArr[2]);
			int y2 = Integer.parseInt(newLineArr[3]);
			
			int result = 0;
			result = arrSum[x2][y2] - arrSum[x1-1][y2] - arrSum[x2][y1-1] + arrSum[x1-1][y1-1];
			
			System.out.println(result);
			
		}

	}

}

 

 

 

 

 

 

 

 

 

[다시] 시간초과

StringTokenizer 빼봄..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class backjoon11660 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer stz = new StringTokenizer(br.readLine());
//		int N = Integer.parseInt(stz.nextToken());
//		int M = Integer.parseInt(stz.nextToken());
		String[] NM = br.readLine().split(" ");
		int N = Integer.parseInt(NM[0]);
		int M = Integer.parseInt(NM[1]);
		
		int[][] arr = new int[N][N];
		
		for(int i=0; i < N; i++) {
			String newLine = br.readLine();
			String[] newLineArr = newLine.split(" ");
			for(int j=0; j < N; j++) {
				arr[i][j] = Integer.parseInt(newLineArr[j]);
			}	
		}
		
		//2차원 배열 출력
//		for(int i=0; i < arr.length; i++) {
//			System.out.println(Arrays.toString(arr[i]));
//		}
		
		for(int i=0; i < M; i++) {
			String newLine = br.readLine();
			String[] newLineArr = newLine.split(" ");
			int x1 = Integer.parseInt(newLineArr[0])-1;
			int y1 = Integer.parseInt(newLineArr[1])-1;
			int x2 = Integer.parseInt(newLineArr[2])-1;
			int y2 = Integer.parseInt(newLineArr[3])-1;
//			System.out.println("("+x1 + "," + y1 + ")~("+x2 + "," + y2 + ")");
			int sum = 0;
			for(int x = x1; x <= x2; x++) {
				for(int y = y1; y <= y2; y++) {
					sum += arr[x][y];
//					System.out.print(arr[x][y]+" ");
				}	
//				System.out.println();
				
			}
			System.out.println(sum);
			
		}

	}

}

 

 

 

 

[다시] 시간초과 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class backjoon11660 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stz.nextToken());
		int M = Integer.parseInt(stz.nextToken());
		
		int[][] arr = new int[N][N];
		
		for(int i=0; i < N; i++) {
			String newLine = br.readLine();
			String[] newLineArr = newLine.split(" ");
			for(int j=0; j < N; j++) {
				arr[i][j] = Integer.parseInt(newLineArr[j]);
			}	
		}
		
		//2차원 배열 출력
//		for(int i=0; i < arr.length; i++) {
//			System.out.println(Arrays.toString(arr[i]));
//		}
		
		
		for(int i=0; i < M; i++) {
			String newLine = br.readLine();
			String[] newLineArr = newLine.split(" ");
			int x1 = Integer.parseInt(newLineArr[0])-1;
			int y1 = Integer.parseInt(newLineArr[1])-1;
			int x2 = Integer.parseInt(newLineArr[2])-1;
			int y2 = Integer.parseInt(newLineArr[3])-1;
//			System.out.println("("+x1 + "," + y1 + ")~("+x2 + "," + y2 + ")");
			int sum = 0;
			for(int x = x1; x <= x2; x++) {
				for(int y = y1; y <= y2; y++) {
					sum += arr[x][y];
//					System.out.print(arr[x][y]+" ");
				}	
//				System.out.println();
				
			}
			System.out.println(sum);
			
		}

	}

}

 

 

 

 

 

 

 

 

---

 

Scanner

- 띄어쓰기, 개행문자를 구분값으로 해 입력값을 읽어들인다. (따로 가공할 필요가 없다.)

- 지원 메소드가 많고, 사용하기 쉽지만 버퍼 사이즈가 1024char이기 때문에 많은 입력을 할 때에는 성능이 좋지 못하다.

BufferedReader

- 버퍼를 사용하지 않는 입력 : 키보드를 통한 입력 즉시 바로 프로그램에 전달

- 버퍼를 사용하는 입력 : 키보드를 통합 입력이 있을 때 한 문자씩 버퍼로 전송.->  버퍼가 가득 차거나 개행문자가 나타나면 버퍼의 내용을 한번에 프로그램에 전달

(외부장치와 하드디스크 간 통신할 때 시간이 많이 걸리기 때문에 

키보드를 누를 때 마다 전송하는 것보다는

중간에 버퍼를 두고 한번에 보내는 것이 더 효과적이다.)

 

- 입력받은 데이터가 String으로 고정된다. -> 형식에 맞게 데이터 가공이 필요하다.(scanner보다 속도는 빠름)

- 버퍼 사이즈는 8192char

- 동기화되기 때문에 멀티 쓰레드 환경에서 안전하다.(scanner는 동기화x)

- 예외처리 반드시 필요. 

readLine()할 때마다 try/catch문으로 감싸거나,

throws IOException을 통해 예외처리.

 

[선언]

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

 

[읽기]

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
String s = br.readLine();

 

[데이터 가공] - StringTokenizer, split사용

// StringTokenizer 
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());

// String.split() 함수
String arr[] = s.split(" ");

- StringTokenizer > nextToken() : readLine()을 통해 입력 받은 값을 공백 단위로 구분하여 순서대로 호출

- String.split() : 배열에 공백단위로 끊어 데이터를 저장하여 사용.

 

 

 

BufferedWriter

- 많은 양을 출력해야 할 때 버퍼를 사용하는 것이 좋다.

- 출력과 개행을 동시에 하지 않기 때문에 개행이 필요하면 newLint();이나 bw.write("\n")을 사용한다.

- BufferedWriter는 사용이 끝나면 반드시 flush() / close()를 해야 한다.

[선언]

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 선언
String str = "abcdef"; // 출력할 문자열
bw.write(s); // 출력
bw.newLine(); // 줄바꿈
bw.flush(); // 남아있는 데이터 모두 출력
bw.close();

[메인 함수]

close()	스트림을 닫음. 닫기 전 flush()해야 함.
flush()	스트림을 비움
newLine()	줄바꿈 역할 수행
write(char[] buf, int offset, int length)	버퍼 offset위치부터 length 크기만큼 출력
write(int c)	한 글자 쓰기
write(String s, int offset, int length)	문자열에서 offset에서부터 일정 길이만큼 출력

 

 

 

StringTokenizer

- 문자열을 지정한 구분자로 쪼개는 클래스, 쪼개진 문자열 = 토큰 (token)

return	function
int	countTokens()	남아있는 token의 개수 반환. (전체 토큰의 개수x / 현재남아있는 토큰 개수)
boolean	hasMoreElements()	커서 바로 앞에 데이터(오프젝트)가 있는지 여부 체크
boolean	hstMoreTokens()	커서 바로 앞에 데이터(토큰)가 있는지 여부 체크
Object	nextElement()	현재 커서가 가리키고 있는 객체를 리턴 후 커서의 위치를 다음 칸으로 이동
String	nextToken()	현재 커서가 가리키고 있는 토큰를 리턴 후 커서의 위치를 다음 칸으로 이동

* 커서 : 현재의 위치를 가리킴 ( 0부터 시작)

InputStreamReader

- 바이트 단위로 읽어들이는 inputStream을 통해 입력을 받은 뒤, 문자 단위로 데이터를 변환시키는 클래스

- 고정된 길이의 데이터만 입력받기 때문에 불편하다. 그래서 BufferReader클래스와 함께사용해서 사용자의 입력을 모두 읽어들인다.