백준 16713 Generic Queries (JAVA 자바 풀이)

백준 16713 Generic Queries (JAVA 자바 풀이)

 

---

 

 

 

---

 

누적합 배열은 구간합 연산 뿐 아니라 R -> L 사이의 연산을 제거하여 복원 작업이 가능한 다른 연산에 대해서도 가능하다. 

 

XOR 연산 역시 이전에 구한 합이 다음 합으로 연결되므로 구간XOR 배열로 구성할 수 있고 슬라이스된 범위에 대해서도 구간합을 구하는 것과 같은 로직으로 구할 수 있다. 

 

이를 수식화 해보면 

 

XOR(arr[L], arr[R]) = acc[R] - acc[L-1]

 

 

구간 XOR 배열을 다음과 같이 구한다. 

 

int[] numbers = new int[N + 1];
int[] Snumbers = new int[N + 1];
for (int i = 1; i <= N; i++) {
   numbers[i] = Integer.parseInt(stringTokenizer.nextToken());
   Snumbers[i] = Snumbers[i - 1] ^ numbers[i];
}

 

 

 

각각의 범위에 대한 연산을 또 다시 XOR로 해주어야 하므로 answer는 ^=를 통해 받는다. 

 

int answer = 0;
for (int i = 0; i < Q; i++) {
   stringTokenizer = new StringTokenizer(bufferedReader.readLine());
   int L = Integer.parseInt(stringTokenizer.nextToken());
   int R = Integer.parseInt(stringTokenizer.nextToken());

   answer ^= Snumbers[R] ^ Snumbers[L - 1];
}

 

 

💡 코드 구현

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

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

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

      int answer = 0;
      for (int i = 0; i < Q; i++) {
         stringTokenizer = new StringTokenizer(bufferedReader.readLine());
         int L = Integer.parseInt(stringTokenizer.nextToken());
         int R = Integer.parseInt(stringTokenizer.nextToken());

         answer ^= Snumbers[R] ^ Snumbers[L - 1];
      }

      System.out.println(answer);
   }

}