백준 28099 이상한 배열 python

세그먼트 트리 2번째 문제
arr[i] == arr[j] ( i < j ) 알때 i+1 ~ j-1 까지 모든 숫자가 arr[i]보다 작으거나 같으면 된다.
그래서 그 구간의 최대값을 찾아서 비교하는 방법을 세그먼트 트리로 적용하여 풀이한다.

📜 문제 바로 가기 : 이상한 배열

제출코드

파이썬

import sys
input = sys.stdin.readline

def merge(a, b):
    if arr[a] >= arr[b]:
        return a
    return b

def buildSegmentTree(node, start, end):
    if start == end:
        segmentTree[node] = start
        return segmentTree[node]
    
    mid = (start + end) // 2;
    left = buildSegmentTree(node*2, start, mid)
    right = buildSegmentTree(node*2 + 1, mid + 1, end)

    segmentTree[node] = merge(left, right)
    return segmentTree[node]

def checkSection(targetStart, targetEnd, node, start, end):
    if targetStart > targetEnd:
        return 0
    
    if targetEnd < start or targetStart > end:
        return 0
    
    if targetStart <= start and end <= targetEnd:
        return node
    
    mid = (start + end) // 2
    left = checkSection(targetStart, targetEnd, node*2, start, mid)
    right = checkSection(targetStart, targetEnd, node*2 +1, mid +1, end)

    if arr[segmentTree[left]] < arr[segmentTree[right]]:
        return right
    return left
    

T = int(input())

for _ in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    arr.append(0)
    segmentTree = [-1] * (4 * N)
    buildSegmentTree(1, 0, N-1)
    segmentTree[0] = N

    numberIndex = [-1] * (N+1)
    flag = True
    for i in range(N):
        num = arr[i]
        if numberIndex[num] == -1:
            numberIndex[num] = i
        else:
            node = checkSection(numberIndex[num]+1, i-1, 1, 0, N-1)
            if arr[segmentTree[node]] > num:
                flag = False
                break
            numberIndex[num] = i
    
    if flag == True:
        print("Yes")
    else:
        print("No")

접근방법

배열을 하나씩 돌면서 숫자를 numberIndex배열에 인덱스로 저장한다.
그 후 똑같은 값이 나오면 처음 나왔던 인덱스를 numberIndex배열에서 확인하고 그 사이의 구간의 최대값을 꺼내 값과 비교하는 방법이다.

이전 문제는 배열값을 업데이트하는 대신 1번 노드만 확인하면 됐는데
이 문제는 배열의 업데이트는 없지만 확인해야되는 노드 구간을 찾아야 된다는 점에서 차이가 있다.