[BOJ] 백준 5676번 음주코딩 (Python)

 

 

 

---

 

☁️ 문제 이해하기

• 문제
  •  입력
    • 첫째 줄: 수열의 크기 n, 게임의 라운드 수 k
    • 둘째 줄: n개의 숫자 xi가 주어짐
    • 세번째 줄부터 마지막 줄(k개의 줄): 명령(c or p) a b
  • 출력
    • 곱셈 명령의 결과를 한 줄에 모두 출력
  • 예시 이해하기

4 6
-2 6 0 -1
C 1 10
P 1 4
C 3 7
P 2 2
C 4 -5
P 1 4
5 9
1 5 -2 4 3
P 1 2
P 1 5
C 4 -5
P 1 5
P 4 5
C 3 0
P 1 5
C 4 -5
C 4 -5

 

☁️ 알고리즘

• 세그먼트 트리 사용하기
  • 이유
    • 하나의 값을 변경(c)하고, 구간 곱을 구하고(p), 곱의 부호를 요구하여 구간 연산이 필요함
    • 세그먼트 트리는 값 변경 혹은 구간 곱을 구하는데 O(logN)의 시간 복잡도를 지님 (빠름)

 

☁️ 코드 뼈대 세우기

• `init(node, start, end)`
  • 입력에 따라 세그먼트 트리 초기화하기 
• `update(node, start, end, index, value)`
  • 세그먼트 트리에서 특정 구간을 수정하기
  • 특정 위치 값이 변경되면 먼저 그 노드의 리프 노드까지도 내려가서 값을 변경
  • 그 후 부모 노드 값 갱신
• `query(node, start, end, left, right)`
  • 특정 구간 left, right의 곱의 부호 계산

 

---

☁️ 코드

import sys

input = sys.stdin.readline

# start, end: 노드가 관리하는 배열의 범위
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
    
    # index가 노드가 관리하는 범위 안이면
    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):
	# 구간 범위가 밖이면 계산에 영향을 주지 않도록 1 반환
    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)	# 세그먼트 트리에서 최악의 경우 필요한 배열의 크기가 4*N이므로 크기를 이렇게 잡음

		# 세그먼트 트리 초기화하기
        init(1, 0, N - 1)

        answer = ""

		# 세그먼트 트리 구간 합 변경 or 구하는 명령 입력받고 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)	# A-1번째 수를 B로 바꾸기
            else:
                check = query(1, 0, N - 1, A - 1, B - 1)	# A-1, B-1 질의할 구간의 범위
                if check == 0:
                    answer += "0"
                elif check > 0:
                    answer += "+"
                else:
                    answer += "-"

        print(answer)

    except:
        break

 

 

☁️ 코드 작성 시 유의할 점

• 1. 양수 음수 0을 판별하는 것이므로 부호만 반환하기
  • 곱한 값을 저장하면 오버플로우가 되더라...
• 2. 테스트 케이스 개수가 주어지지 않아 try-except 문을 사용해 처리해줘야 함
• 3. input 중 string과 integer가 함께 주어져 있는 것이 있어 map을 사용하지 않고 split만 사용한 다음 숫자는 나중에 integer로 변환해줌