백준 19951 태상이의 훈련소 생활 (JAVA 자바 풀이)

백준 19951 태상이의 훈련소 생활 (JAVA 자바 풀이)

 

---

 

 

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

 

---

 

문제에서 설명하듯이 주어지는 조교의 쿼리를 모두 다 받아놓고 한번에 연산을 해주어야 한다. 

 

문제에서 N, M의 조건이 최대 10만이기 때문에 반복문 두번이면 O(n^2)으로 1초를 넘어서게 될 것이 분명하다. 

 

누적합을 이용해 풀이해야 한다. 문제는 누적합을 어떻게 설계할 것이냐이다. 

 

만약 누적합이라고 하여, 또 M번의 쿼리를 그대로 모든 배열에 넣는 방식을 사용하면 N이 10만 건으로 주어질 경우 배열의 10만 개의 칸을 순회해야 한다. 즉, 앞에서 모든 계산을 받자마자 그대로 하는 것과 다를 바가 없어진다. 

 

따라서 이 부분의 시간 복잡도를 O(M)으로 유지할 수 있어야 한다.

int[] groundS= new int[N+2];

while(M-->0){
   stringTokenizer = new StringTokenizer(bufferedReader.readLine());
   int start = Integer.parseInt(stringTokenizer.nextToken());
   int end = Integer.parseInt(stringTokenizer.nextToken());
   int k = Integer.parseInt(stringTokenizer.nextToken());

}

 

아이디어는 누적합 배열을 구성할 때 모든 숫자를 넣는 것이 아니라, 처음과 끝만 기록하는 것이다. 

 

즉 다음과 같다. 

 

   groundS[start] = groundS[start] + k;
   groundS[end+1] = groundS[end+1] + (-k);

 

k 값은 주어진 값이며 -k는 주어진 값의 반대 부호 값이다. 이 값은 주어진 길이의 마지막 +1 인덱스에 추가해준다.

왜 이러한 작업이 필요할까?

 

연산을 해줄 때 첫 번째 쿼리인 1 5 -3을 살펴보자. 

 

만약 쿼리가 위의 것 하나 뿐이라면 마지막에 최종적인 누적 배열을 구성할 때

[_ 0 0 0 0 0 0 0 0 0 0] 배열이 

 

[_ -3 -3 -3 -3 -3 0 0 0 0 0 ]

으로 초기화되어야 한다. 

 

이를 누적 배열로 설정하고 있기 때문에 하나하나 값을 채워주는 것이 아니라 start부터 end까지 쭈욱 이어지는 개념으로 초기화를 시켜야 하고, 이는 각 인덱스에 따른 값은 이전 값을 통해 구해진다는 것을 의미한다. 

즉, S2 = S1 + S2이다. 

 

이때 끝나는 지점을 설정해주어야 하므로 1 ~ 5까지 -3이 초기 값 0과 더해지면서 -3으로 채워지고, 6부터는 이전의 -3을 다시 원상복구 해주기 위해 +3과 더해주면 이후부터는 0으로 채워질 수 있게 된다. 

 

따라서 최종 연산을 위한 합배열은 다음과 같이 구할 수 있다. 

 

for (int i =1; i<groundS.length; i++){
   groundS[i] = groundS[i-1] + groundS[i];
}

 

예시로 주어진 쿼리에 대해 각 쿼리마다 채워지는 실제 배열 값들을 살펴보면 다음과 같다. 

 

0) 초기 상태 

 

1) 1 5 -3 수행 후 

2) 6 10 5 수행 후 

 

 

3) 2 7 2 수행후 

 

 

 

최종 합 배열 

 

 

 

이제 이렇게 구한 숫자를 처음 ground 배열의 각 index와 합쳐주기만 하면 된다. 

 

for(int i=1;i<ground.length; i++){
   ground[i] = ground[i] + groundS[i];
}

 

모든 반복문에서 최대 시간 복잡도가 O(N)을 넘지 않으므로 조건을 만족하며 풀이할 수 있다. 

 

 

💡 코드 구현

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

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int N = Integer.parseInt(stringTokenizer.nextToken());
      int M = Integer.parseInt(stringTokenizer.nextToken());

      int[] ground = new int[N + 1];
      stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      for (int i = 1; i <= N; i++) {
         ground[i] = Integer.parseInt(stringTokenizer.nextToken());
      }

      int[] groundS = new int[N + 2];
      while (M-- > 0) {
         stringTokenizer = new StringTokenizer(bufferedReader.readLine());
         int start = Integer.parseInt(stringTokenizer.nextToken());
         int end = Integer.parseInt(stringTokenizer.nextToken());
         int k = Integer.parseInt(stringTokenizer.nextToken());

         groundS[start] = groundS[start] + k;
         groundS[end + 1] = groundS[end+1] + (-k);
      }

      for (int i = 1; i <= N; i++) {
         groundS[i] = groundS[i - 1] + groundS[i];
      }

      for (int i = 1; i <=N; i++) {
         ground[i] = ground[i] + groundS[i];
      }

      StringBuilder stringBuilder = new StringBuilder();
      IntStream.range(1, ground.length).forEach(i -> stringBuilder.append(ground[i]).append(" "));
      System.out.println(stringBuilder);
   }
}