BOJ 18917 수열과 쿼리 38

By kuper0201

Published in 알고리즘

2021-03-05

1 min read

문제

입력

풀이

문제

BOJ 18917 수열과 쿼리 38 바로 가기

처음에 0이 하나 포함되어있는 배열 A가 있다. 이때, 다음 쿼리를 수행해야 한다.

1 x: A의 가장 뒤에 x를 추가한다.

2 x: A에서 x를 제거한다. A에 x가 두 개 이상 있는 경우에는 가장 앞에 있는 하나만 제거한다. 항상 A에 x가 있는 쿼리만 주어진다.

3: A에 포함된 모든 원소를 더한 값을 출력한다.

4: A에 포함된 모든 원소를 XOR한 값을 출력한다.

입력

첫째 줄에는 쿼리의 개수 M이 주어진다. 둘째 줄부터 다음 M 개의 줄에 쿼리가 주어진다.

풀이

문제에 제시된 조건을 단순히 구현만 하면 될 것으로 보이지만 구현 해 보면 시간 초과가 발생한다.

시간 초과가 발생하는 이유를 살펴보면 3번, 4번 쿼리가 들어 올 때마다 전체 배열을 순회하며 덧셈 연산과 XOR 연산을 하기 때문이다.

일단 덧셈 연산에서 시간 초과를 해결하기 위해서는 배열에 데이터가 추가될 때는 별도의 변수에 덧셈 연산을 하고, 배열에서 데이터가 빠질 때는 뺄셈 연산을 통해 원본 값을 복원하면 된다는 사실은 쉽게 유추가 가능하다.

XOR연산에서도 마찬가지로 배열에 데이터가 추가 될 때는 별도의 변수에 데이터를 XOR연산을 통해 추가 하고, 데이터가 빠질 때는 원본 값을 복원하면 된다.

하지만 XOR연산은 덧셈/뺄셈과 다르게 원본을 복원하는 방법을 직관적으로 알기 어렵다.

결론부터 말하자면 XOR연산을 통해 도출된 값에 다시 XOR연산을 하면 원본값을 추출 할 수 있다.

원리를 설명하기 전에 상기해야 할 XOR의 성질이 존재한다.

XOR연산은 결합 법칙이 성립한다는 성질이다.

A와 B를 XOR 연산하면 다음과 같다.

A\bigoplus{B}

XOR을 진행한 값에 B를 다시 XOR 연산을 하면 다음과 같은 식을 유도 할 수 있다.

A\bigoplus{B}\bigoplus{B}

XOR연산은 결합 법칙이 성립하므로 위의 식은 다음과 같은 식으로 변환 할 수 있을 것이다.

A\bigoplus({B}\bigoplus{B})

XOR 연산에서는 같은 값을 연산하면 언제나 0이라는 값이 나온다. 따라서 위의 식은 다음과 같이 계산 될 것이다.

A\bigoplus{0}

또한 하나의 값과 0을 XOR 하면 언제나 A 값이 결과가 된다. 따라서 위의 식을 정리하면 다음과 같다.

A\bigoplus({B}\bigoplus{B}) = A\bigoplus{0} = A

A의 값이 XOR연산을 진행 하기 전의 원본 값이므로 같은 값으로 두 번 연산하면 원본 값이 결과가 된다는 것을 알 수 있다.

이제 해당 쿼리별 연산을 처리하는 코드를 구현하면 문제를 해결 할 수 있다.

코드 보기(Java)

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        // 쿼리 개수 입력
        int M = Integer.parseInt(br.readLine());
        long sum = 0, res = 0;
        
        // 쿼리 입력 받으며 연산 처리
        for(int i = 0; i < M; i++) {
            String[] str = br.readLine().split(" ");

            int cmd = Integer.parseInt(str[0]);
            int oper = 0;

            if(str.length != 1) oper = Integer.parseInt(str[1]);

            if(cmd == 1) {
                sum += oper;
                res ^= oper;
            } else if(cmd == 2) {
                sum -= oper;
                res ^= oper;
            } else if(cmd == 3) sb.append(sum +"\n");
            else sb.append(res +"\n");
        }

        System.out.println(sb);
    }
}

코드 보기(C++)

#include <iostream>
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

using namespace std;

int main() {
    fastio;
    
    // 쿼리 개수 입력
    int M;
    long sum = 0, res = 0;
    cin >> M;
    
    // 쿼리 입력 받으며 연산 처리
    for(int i = 0; i < M; i++) {
        int cmd, oper;
        cin >> cmd;
        
        if(cmd == 1) {
            cin >> oper;
            sum += oper;
            res ^= oper;
        } else if(cmd == 2) {
            cin >> oper;
            sum -= oper;
            res ^= oper;
        } else if(cmd == 3) cout << sum << endl;
        else cout << res << endl;
    }
    
    return 0;
}

코드 보기(Kotlin)

fun main(args: Array<String>) {
    // 쿼리 개수 입력
    var M = readLine()!!.toInt()
    var sum = 0L
    var res = 0L
    
    // 쿼리 입력 받으며 연산 처리
    for (i in 0 until M) {
        var s = readLine()!!.split(" ")
        var cmd = s[0].toInt()
        
        if (cmd == 1) {
            var oper = s[1].toLong()
            sum += oper
            res = res xor oper
        } else if(cmd == 2) {
            var oper = s[1].toLong()
            sum -= oper
            res = res xor oper
        } else if(cmd == 3) {
            println(sum)
        } else {
            println(res)
        }
    }
}

코드 보기(Python)

from sys import stdin

def main():
    # 쿼리 개수 입력
    M = int(stdin.readline())
    sum = 0
    res = 0
    
    # 쿼리 입력 받으며 연산 처리
    for i in range(M):
        s = stdin.readline().split(' ')
        cmd = int(s[0])
        
        if cmd == 1:
            oper = int(s[1])
            sum = sum + oper
            res = res ^ oper
        elif cmd == 2:
            oper = int(s[1])
            sum = sum - oper
            res = res ^ oper
        elif cmd == 3:
            print(sum)
        else:
            print(res)
            
if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    // 쿼리 개수 입력
    var M = Int(readLine()!)!
    var sum : UInt64 = 0
    var res : UInt64 = 0

    // 쿼리 입력 받으며 연산 처리
    for i in 0..<M {
        var s = readLine()!.split(separator: " ")
        var cmd = UInt64(s[0])!
        
        if cmd == 1 {
            var oper = UInt64(s[1])!
            sum += oper
            res ^= oper
        } else if cmd == 2 {
            var oper = UInt64(s[1])!
            sum -= oper
            res ^= oper
        } else if cmd == 3 {
            print(sum)
        } else {
            print(res)
        }
    }
}

main()