[JAVA] 백준 2042번 구간 합 구하기

[HAVE TO DO]

STUDYING : JAVA

---

문제링크 : https://www.acmicpc.net/problem/2042

 

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

public class Main {
	
	static int N, M, K;
	static long sum;
	static int[] nums;
	static Information[] info;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		nums = new int[N];
		
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());
			nums[i] = num;
		}
		
		info = new Information[M+K];
		
		for (int i = 0; i < M + K; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			info[i] = new Information(a, b, c); 
		}
		
		for (int i = 0; i < M + K; i++) {
			if(info[i].a == 1) {
				nums[info[i].b - 1] = info[i].c;
			}
			else if(info[i].a == 2) {
				sum = 0;
				for (int j = info[i].b - 1; j < info[i].c; j++) {
					sum += nums[j];
				}
				System.out.println(sum);
			}
		}
		
		br.close();

	}

}

class Information {
	int a;
	int b;
	int c;
	
	public Information(int a, int b, int c) {
		super();
		this.a = a;
		this.b = b;
		this.c = c;
	}

	@Override
	public String toString() {
		return "Change [a=" + a + ", b=" + b + ", c=" + c + "]";
	}
	
}

누구나 생각할 수 있는 단순한 구조로 했더니 시간이 엄청 걸렸다. (당연하다....

 

웃안웃...

 

세그먼트 트리를 이용하여 짜면 시간이 훨씬 줄어든다고 한다.

세그먼트 트리 구현은 여러 글을 참고해서 짰다.

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

public class Main {
	
	static int N, M, K;
	static int[] nums;
	static long[] tree;
	static Information2[] info;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		nums = new int[N+1];
		
		for (int i = 1; i <= N; i++) {
			int num = Integer.parseInt(br.readLine());
			nums[i] = num;
		}
		
		//4를 곱하면 모든 범위를 커버할 수 있음
		tree = new long[4*N];
		
		info = new Information2[M+K];
		for (int i = 0; i < M + K; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			info[i] = new Information2(a, b, c); 
		}
		
		makeTree(1, N, 1);
		
		for (int i = 0; i < M + K; i++) {
			if(info[i].a == 1) {
				int diff = info[i].c - nums[info[i].b];
				nums[info[i].b] = info[i].c;
				update(1, N, 1, info[i].b, diff);				
			} else if(info[i].a == 2) {
				System.out.println(sum(1, N, 1, info[i].b, info[i].c));
			}
		}

	}
	
	// start: 시작 인덱스, end: 끝 인덱스
	static long makeTree(int start, int end, int node) {
		if(start == end) return tree[node] = nums[start];
		int mid = (start + end) / 2;
		//재귀적으로 두 부분으로 나눈 뒤에 그 합을 자기 자신으로 함
		tree[node] = makeTree(start, mid, node * 2) + makeTree(mid + 1, end, node * 2 + 1);
		return tree[node];
	}
	
	// start: 시작 인덱스, end: 끝 인덱스, left&right: 구간 합을 구하고자 하는 범위
	static long sum(int start, int end, int node, int left, int right) {
		//범위 밖에 있는 경우
		if(left > end || right < start) return 0;
		//범위 안에 있는 경우
		if(left <= start && end <= right) return tree[node];
		//그렇지 않다면 두 부분으로 나누어 합을 구하기
		int mid = (start + end) / 2;
		return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
	}
	
	// start: 시작 인덱스, end: 끝 인덱스, index: 구간 합을 수정하고자 하는 노드, diff: 수정할 값
	static void update(int start, int end, int node, int index, int diff) {
    	//범위 안에 있는 경우
		if(start <= index && index <= end) tree[node] += diff;
		else return;
		if(start == end) return;
		int mid = (start + end) / 2;
		update(start, mid, node * 2, index, diff);
		update(mid + 1, end, node * 2 + 1, index, diff);
	}
}

class Information2 {
	int a;
	int b;
	int c;
	
	public Information2(int a, int b, int c) {
		super();
		this.a = a;
		this.b = b;
		this.c = c;
	}

	@Override
	public String toString() {
		return "Change [a=" + a + ", b=" + b + ", c=" + c + "]";
	}
	
}

참고하지 않고 내가 짤 수 있기 위해서는 몇 번 더 짜봐야할 것 같다. 아무튼 세그먼트 트리의 구조는 이해함!

구간 합 구할 때 자주 사용한다고 한다.

 

시간이 1/5로 줄었다