백준 18436 : 수열과 쿼리 37 (Python)

본문 링크

import sys
input=sys.stdin.readline

def init(node , start ,end):

    if start==end:
        if L[start]%2==0:
            tree[node][0]=1
        else:
            tree[node][1]=1

    else:
        mid=(start+end)//2

        init(node*2 , start , mid)
        init(node*2+1 , mid+1 , end)

        tree[node]=[tree[node*2][0]+tree[node*2+1][0] , tree[node*2][1]+tree[node*2+1][1] ]
    return tree[node]

def update(node,  start , end , index , value):

    if index<start or index>end:
        return

    if start==end:
        if value%2==0:
            tree[node]=[1,0]
        else:
            tree[node]=[0,1]
        return tree[node]

    mid=(start+end)//2

    update(node*2 , start , mid , index , value)
    update(node*2+1 , mid+1 , end , index , value)

    tree[node] = [tree[node * 2][0] + tree[node * 2 + 1][0], tree[node * 2][1] + tree[node * 2 + 1][1]]

def query(node, start , end , left , right):

    if left>end or right<start:
        return [0,0]

    if left<=start and right>=end:
        return tree[node]

    mid=(start+end)//2
    left_node=query(node*2 , start , mid , left , right)
    right_node=query(node*2+1 , mid+1 , end , left , right)

    return [left_node[0]+right_node[0] , left_node[1]+right_node[1]]


N=int(input())
tree=[[0,0] for _ in range(N*4)]
#tree=[ [0,0] ] *(N*2)

L=list(map(int,input().split()))

init(1,0,N-1)

for i in range(int(input())):

    Q,A,B=map(int,input().split())

    if Q==1:
        if L[A-1]%2==B%2: # 둘다 짝수거나 홀수라면
            L[A-1]=B
            continue
        else:
            update(1,0,N-1,A-1,B)
            L[A-1]=B
    elif Q==2:
        print(query(1,0,N-1,A-1,B-1)[0])
    else:
        print(query(1,0,N-1,A-1,B-1)[1])

📌 어떻게 접근할 것인가?

세그먼트 트리를 사용해 풀었습니다. 2차원 배열로 만들어 주었습니다.

파이썬에서 배열을 생성하는 과정에서 맞왜틀을 자주 했는데

처음에 배열을 이렇게 생성했습니다.

tree=[ [0,0] ] *(N*4)

하지만 이렇게 해버리면 2차원 배열은 절대 이렇게 만들어서 안됩니다.

2차원 배열은 무조건 컴프리헨션을 사용해야합니다.

# N X M 크기의 2차원 리스트 초기화
n = 3
m = 4
arr = [[0] * m] * n
print(arr) # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

arr[1][1] = 7
print(arr) # [[0, 7, 0, 0], [0, 7, 0, 0], [0, 7, 0, 0]]

컴프리핸선을 사용하지 않으면 다음과 같은 오류가 발생합니다.

이러한 현상은 내부적으로 포함된 3개의 리스트가 모두 동일한 객체의 3개에 대한 참조값으로 여겨지기 때문입니다. 따라서 특정 크기를 갖는 2차원 리스트를 초기화할 때는 반드시 리스트 컴프리헨션을 사용해야 합니다.

파이썬을 거의 1년동안 쓰면서 처음알았는데 꼭 기억해야할 부분인것 같습니다.

이후 세그먼트 트리는 init 함수를 통해서 입력받은 리스트에 대한 초기값을 할당하고
update 함수를 통해서 배열의 값을 변경했습니다.

이때 $A$ 와 $B$ 가 둘다 짝수이거나 홀수인경우는 넘깁니다.

이후 query 함수를 통해 2차원 배열을 return 함으로써 특정 구간의 홀/짝수의 개수를 반환하도록 하였습니다.