[백준] 1275번 : 커피숍2 - 자바(JAVA)

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

1275번: 커피숍2

 

문제 해석

N개의 정수를 가지고 게임을 한다.

우리는 심판 역을 맡았기 때문에 질문에 대한 답들을 미리 알아야 한다.

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.

둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어집니다.

셋째 줄부터 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어집니다.

 

한 턴마다 구한 합을 한 개씩 출력합니다.

 

문제 풀이 전 설계

단순하게 접근해 본다면 배열을 기록해두고 x~y까지의 합을 구하고 , a번째 수를 b로 바꾸는 아주 단순한 문제 같습니다.

그러면서 결과를 StringBuilder에 쌓아 마지막에 출력하면 끝?

 

하지만 최악의 시간 복잡도를 고려해보면 N의 개수와 Q의 범위는 1~100,000입니다.

100,000 * 100,000 = 10,000,000,000(백억)

 

즉, O(N^2)으로는 해결할 수 없습니다.

 

입력되는 모든 수는 int형 정수가 들어오지만 이들의 합은 int형 보다 크거나 작을 수 있기 때문에 long 타입을 사용합니다.

 

또한 문제에서 x> y 인 경우에는 y번째부터 x번째입니다.

 

시간 복잡도를 어떻게 줄여야 할까요?

이전에 미리 계산한 값들을 미리 기록한 후 사용해야 할 것 같습니다.

 

하지만 계산해 놓았던 값들이 바뀔 수 있는데 어떻게 해야 할까요?

계산한 값들의 시작 인덱스, 종료 인덱스, 계산된 값을 저장해 놓고 만약 인덱스 범위에 해당하는 수가 수정된다면 

계산된 값에 해당하는 인덱스의 수를 빼고,  바꾼 데이터를 더하여 갱신합니다.

문제 풀이하면서

핵심 로직

for (int i = 0; i < Q; i++) {
		st = new StringTokenizer(br.readLine(), " ");
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		int minIndex = Math.min(x, y) - 1;
		int maxIndex = Math.max(x, y) - 1;

		// subTotals에 존재하는거라면?
		for (SubTotal e : subTotals) {
						

		// subTotals에 존재하지 않는다면
		int sum = 0;
		for (int j = minIndex; j <= maxIndex; j++) {
			sum += numbers[j];
			subTotals.add(new SubTotal(minIndex, maxIndex, sum));
		}

		}

위처럼 구현해보려 했지만 과연 subTotals에 존재한다는 것이 어떠한 의미로써 사용되어야 함을 정의할 수 없어 시도하지 못했습니다.

 

예를 들어 e.startIndex 와 e.finalIndex가 minIndex와 maxIndex사이에 존재한다면? 이는 분명히 부분합입니다.

하지만 하지만 부분합이 여러 개 존재한다면? 어떤 것을 가져다가 사용해야 할지 이런 부분들을 정의할 수 없었습니다.

 

세그먼트 트리를 사용하여 부분합을 구하는 문제라고 합니다.

 

다음을 참고하시면 세그먼트 트리에 대해서 어느 정도 이해하실 수 있습니다.

https://junuuu.tistory.com/197?category=987844 

세그먼트 트리란?

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main_1275_커피숍2 {

	static long[] segmentTree;
	static int[] numbers;

	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 Q = Integer.parseInt(st.nextToken());

		numbers = new int[N];

		// 수 입력
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}

		// Segment tree 만들기
		segmentTree = new long[4 * N];
		makeSegmentTree(0, N - 1, 1);

		// x~y까지의 합을 구하고 , a번째 수를 b로 바꾸어라
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken());

			int minIndex = Math.min(x, y);
			int maxIndex = Math.max(x, y);

			sb.append(sum(0, N - 1, 1, minIndex, maxIndex) + "\n");
			// numbers[a]는 기존값이기 때문에 기존값을 빼주고 갱신값을 더해주는 방식

			update(0, N - 1, 1, a, (long)b - numbers[a]);
			numbers[a] = b;

			// update2(0, N-1, 1, a, b);
		}

		System.out.println(sb);

	}

	// start = 배열의 시작 인덱스, end = 배열의 끝 인덱스, index = 노드의 번호
	static long makeSegmentTree(int start, int end, int index) {
		if (start == end) {
			return segmentTree[index] = numbers[start];
		}
		int mid = (start + end) / 2;
		return segmentTree[index] = makeSegmentTree(start, mid, index * 2)
				+ makeSegmentTree(mid + 1, end, index * 2 + 1);
	}

	// start = 배열의 시작 인덱스, end = 배열의 끝 인덱스, index = 노드의 번호
	// left, right = 구간 합을 구하고자 하는 범위
	static long sum(int start, int end, int index, int left, int right) {
		// 범위 밖에 있는 경우
		if (left > end || right < start)
			return 0;
		// 범위 안에 있는 경우
		if (left <= start && end <= right)
			return segmentTree[index];
		// 그렇지 않다면 두 부분을 나누어 합을 구하기
		int mid = (start + end) / 2;
		return sum(start, mid, index * 2, left, right) + sum(mid + 1, end, index * 2 + 1, left, right);

	}

	public static void update(int start, int end, int index, int originIndex, long diff) {
		// 범위 밖에 있는경우에는 진행하지 않습니다.
		if (originIndex < start || originIndex > end) {
			return;
		}
		
		// 범위 안에 있는경우에는 값을 갱신합니다.
		segmentTree[index] += diff;
		
		// 리프노드일 경우에는 더이상 진행x
		if (start == end) {
			return;
		}
			
		// 리프노드가 아닌경우에는 리프노드까지 진행
		int mid = (start + end) / 2;
		update(start, mid, index * 2, originIndex, diff);
		update(mid + 1, end, index * 2 + 1, originIndex, diff);

	}

	static long update2(int start, int end, int index, int originIndex, long newValue) {
		// 범위 밖이라면 tree값 그대로 반환
		if (originIndex < start || originIndex > end) {
			return segmentTree[index];
		}

		// 리프 노드라면 NewValue로 초기화
		if (start == end) {
			return segmentTree[index] = newValue;
		}

		// 재귀적으로 올라가면서 tree값 재구성
		int mid = (start + end) / 2;
		return segmentTree[index] = update2(start, mid, index * 2, originIndex, newValue)
				+ update2(mid + 1, end, index * 2 + 1, originIndex, newValue);
	}

}