백준 18917 자바 - 수열과 쿼리 38 (BOJ 18917 JAVA)

문제 : boj18917

 

  제거 연산이 '항상 A에 x가 있는 쿼리만 주어진다' 라는 조건이 있으므로 상당히 간단해지는 문제이다. 애초에 뭐 가장 앞에 있는걸 제거한다는 부분도 딱히 의미가 없다. 아무튼 있는 값에 대해서만 제거가 되므로 편하게 할 수 있다.

 

 

1. 모든 원소를 더한 값  sum과 같이 변수를 하나 두고 1 x 형태의 연산이 들어올 때 더해두고, 2 x 형태의 연산이 들어올 때 빼두면 된다.

 

 

2. 모든 원소를 XOR한 값  이게 좀 어려울 수 있다. 일단 1 x 형태의 연산은 그냥 XOR을 하면 된다. ('^' 연산)2 x 형태가 문제인데, 사실 이것도 그냥 XOR을 하면 된다. 왜냐면 어떠한 수 n에 대해 n^n = 0 이다. 즉 자기 자신을 빼내는 것 역시 XOR로 동일한 수를 진행하면 되는 것이다.

 

 

3. 전체 로직

  1 x, 2 x 형태의 연산에 대해 두 변수에 각각 더한 값과 xor한 값을 저장한다. 그리고 3과 4 형태의 연산에 대해 바로바로 출력만 해주면 된다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    private void solution() throws Exception {
        int m = nextInt();
        long sum = 0;
        long xor = 0;
        StringBuilder sb = new StringBuilder();
        while (m-->0) {
            int a = nextInt();
            int b = a<=2?nextInt():0;
            switch(a) {
                case 1 :
                    sum+=b;
                    xor^=b;
                    break;
                case 2 :
                    sum-=b;
                    xor^=b;
                    break;
                case 3 : sb.append(sum).append('\n'); break;
                case 4 : sb.append(xor).append('\n'); break;
            }
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}