백준/ Gold 1 문제 , 백준 파이썬 5670 , 음주 코딩 [세그먼트 트리]

백준/ Gold 1 문제 , 백준 파이썬 5670 , 음주 코딩 [세그먼트 트리]

 

 

풀이 시간

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
기존에 0이나 음수였던부분을 바꾸게 되면 어떻게 처리를 해야할까 고민하고 접근하는 부분이 약간 까다로웠음.
어차피 연산은 부호만 확인하면 되기때문에 1,-1,0 의 숫자들만 가지고 연산을 한다.

 

 

문제 출처

 

https://www.acmicpc.net/problem/5676

5676번: 음주 코딩

 

 

 

 

풀이

 

 

중요한 부분들만 풀이를 적어보겠다.

 

 

1. 세그먼트 트리 생성

 

배열에 저장된 값이 양수,음수,0 인지 확인하고 리프노드에 저장한다.

 

이후 부모노드들은 자식노드의 곱의 부호를 확인해가며 저장한다.

 

 

2. 특정 부분 교체 함수

 

기존 세그먼트 트리 로직이랑 똑같다.

 

여기서 마지막 줄 코드를 꼭 넣어줘야 하는데, 0이였던가 음수였던 자리를 새로 초기화해줘서 그에 맞는 부호들을 새로 저장해 나아갈 수 있게 해준다.

 

 

 

 

3. 입력 받기 및 각 함수 호출

 

 

새로 넣을 값이 양수,음수,0 인지 확인하고 그에 맞는 값을 update 파라미터에 넣어 호출한다.

 

결과값도 똑같이 확인하여 그에 맞는 부호나 0을 출력시키면 된다.

 

 

 

 

정답

 

 

 

import sys
input=sys.stdin.readline

def init(start,end,index):
    if start==end:
        if arr[start]>0:
            tree[index]=1
        elif arr[start]<0:
            tree[index]=-1
        else:
            tree[index]=0
    else:
        mid=(start+end)//2
        tree[index]=init(start,mid,index*2)*init(mid+1,end,index*2+1)
    return tree[index]

def update(start,end,index,w,v):
    if w<start or w>end:
        return
    if start==end:
        tree[index]=v
        return tree[index]
    mid=(start+end)//2
    update(start,mid,index*2,w,v)
    update(mid+1,end,index*2+1,w,v)
    tree[index]=tree[index*2]*tree[index*2+1]
    
def rangeGop(start,end,index,left,right):
    if left>end or start>right:
        return 1
    if start>=left and right>=end:
        return tree[index]
    mid=(start+end)//2
    return rangeGop(start,mid,index*2,left,right)*rangeGop(mid+1,end,index*2+1,left,right) 
    
while True:
    try:
        N,M=map(int,input().split())
        arr=list(map(int,input().split()))
        tree=[0]*(N*4)
        
        init(0,N-1,1)
        
        for i in range(M):
            a,b,c,=input().split()
            b,c=int(b),int(c)
            if a=='C':
                arr[b-1]=c
                if c<0:
                    update(0,N-1,1,b-1,-1)
                elif c>0:
                    update(0,N-1,1,b-1,1)
                else:
                    update(0,N-1,1,b-1,0)
            elif a=='P':
                answer=rangeGop(0,N-1,1,b-1,c-1)
                if answer>0:
                    print('+',end='')
                elif answer<0:
                    print('-',end='')
                else:
                    print(0,end='')
        print()
    except:
        break