[백준] 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번 쿼리가 등장할 때마다, 답을 한 줄에 하나씩 출력한다.

제한

1 ≤ M ≤ 500 000
1 ≤ x ≤ 1 000 000 000
3번 혹은 4번 쿼리가 적어도 하나 주어진다.

내 풀이

import sys
input = sys.stdin.readline

m = int(input())

sum1 = 0
xor1 = 0
for _ in range(m):
    calc = input().split()
    if calc[0] == '1':
        sum1 += int(calc[1])
        xor1 ^= int(calc[1])
    elif calc[0] == '2':
        sum1 -= int(calc[1])
        xor1 ^= int(calc[1])
    elif calc[0] == '3':
        print(sum1)  
    elif calc[0] == '4':
        print(xor1)

코멘트

처음에는 곧이 곧대로 A 배열에 append, remove, sum, 반복문으로 XOR 연산을 했다가 시간 초과를 받았다. 시간 초과 없이 효율적으로 풀기 위해서는 배열 연산을 그대로 하지 말고 합과 XOR 결과를 미리 계산해두는 것이다. 1의 경우 x를 배열에 추가하는 것이므로 sum은 x를 더해야 한다. 2의 경우 x 중 하나만 삭제하는 것이므로 sum에서 x를 빼면 된다.

XOR 연산이란 비트단위로 동작하는 연산으로, 수를 이진수로 변환하여 자리수끼리 수가 같으면 0, 다르면 1로 변환하는 것이다. 파이썬에서 XOR 연산자는 ^이다. 3^5 연산의 예를 들면 3을 이진수로 표현하면 (0)11, 5를 이진수로 표현하면 101이므로 앞자리수부터 0^1 = 1, 1^0=1, 1^1=0이 되어 3^5 = $110_2$ = 6이 된다.

아무튼 합 뿐만 아니라 XOR 연산자도 그 때 그 때 계산을 해 두는데 1일 경우에는 바로 ^=를 하면 되고, 2일 때도 ^=를 하면 된다. (같은 수를 ^하면 원래대로 되는 효과가 있는 듯)

[백준] 18917 수열과 쿼리 38

문제

입력

출력

제한

내 풀이

코멘트

References