백준 5676 : 음주 코딩 (Python)

본문 링크

import sys

input = sys.stdin.readline


def init(node, start, end):
    if start == end:
        tree[node] = L[start]
        return

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

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


def update(node, start, end, index, value):
    if index < start or index > end:
        return

    if start == end:

        if value > 0 :
            tree[node] = 1
        elif value == 0:
            tree[node] = 0
        else:
            tree[node] = -1

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

    check = tree[node * 2] * tree[node * 2 + 1]

    if check > 0:
        tree[node] = 1
    elif check == 0:
        tree[node] = 0
    else:
        tree[node] = -1


def query(node, start, end, left, right):
    if left > end or right < start:
        return 1

    if left <= start and right >= end:  # 포함하고 있다면.

        if tree[node] > 0:
            tree[node] = 1
            return 1
        elif tree[node] == 0:
            tree[node] = 0
            return 0
        else:
            tree[node] = -1
            return -1

    return query(node * 2, start, (start + end) // 2, left, right) * query(node * 2 + 1, (start + end) // 2 + 1, end,left, right)


while True:
    try:
        N, K = map(int, input().split())
        L = list(map(int, input().split()))
        tree = [0] * (4 * N)

        init(1, 0, N - 1)

        Answer = ""

        for i in range(K):
            Q, A, B = input().split()

            A = int(A);
            B = int(B)

            if Q == "C":
                update(1, 0, N - 1, A - 1, B)
            else:
                check = query(1, 0, N - 1, A - 1, B - 1)
                if check == 0:
                    Answer += "0"
                elif check > 0:
                    Answer += "+"
                else:
                    Answer += "-"

        print(Answer)

    except:
        break

📌 어떻게 접근할 것인가?

세그먼트 트리를 사용했습니다.

쿼리는 2개 입니다. 특정인덱스의 값을 바꾸는것 , 그리고 특정범위내의 곱의 음수인지 양수인지 0 인지 판단하는것.

값을 바꾸는것은 그냥 구현하면 되는데 이때 특정 구간의 전체 곱을 그대로 구해버리면 수가 너무 커지기 때문에 시간초과가 발생합니다.

구하고자 하는것은 양수 , 음수 , 0 을 판별하는 것이므로 그것에 맞게 각각 1 , -1 , 0 을 반환해서 시간복잡도를 줄어야 합니다.

또한 테스트 케이스의 개수는 주어지지 않기 때문에 while 문과 try-except 를 사용해야합니다.