글 읽기 - 파이썬, 세그먼트 트리 이용하여 풀었는데 시간초과가 납니다.

yanghs0540 2년 전 0

세그먼트 트리를 이용한 풀이 방법이 있다길레 검색해보고 한번 해봤는데 시간초과가 납니다.

같은 문제에 수열의 크기만 작은

11053 : 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/proble...

문제에 제출해보았는데 답은 맞았다고 나오는데

혹시 제가 잘못 구현한 부분이 있을까요?

tree = []

def find_max_val(node_id, start, end, left, right):
    '''
    :param node_id: 트리의 노드 id 
    :param start: 트리 탐색 시작 지점
    :param end: 트리 탐색 종료 지점
    :param left: 찾고자 하는 구간 시작 지점
    :param right: 찾고자 하는 구간 종료 지점
    :return: 찾고자 하는 구간의 최댓값
    '''
    # 범위 밖이면 0을 반환, 재귀가 반복될 수록 end 는 줄어들고 start는 커지므로 범위체크를 한다.
    if left > end or right < start:
        return 0
    # 범위 안이면 현재 값 반환
    if left <= start and end <= right:
        return tree[node_id]
    mid = (start + end) // 2
    ret = max(find_max_val(node_id * 2 + 1, start, mid, left, right),
              find_max_val(node_id * 2 + 2, mid + 1, end, left, right))
    return ret


def update(node_id, start, end, idx, val):
    '''
    :param node_id: 트리의 노드 id 
    :param start: 트리 탐색 시작 지점
    :param end: 트리 탐색 종료 지점
    :param idx: 변경할 인덱스
    :param val: 변경할 값
    '''
    if idx > end or idx < start:
        return
    if start == end:
        tree[node_id] = val
        return

    mid = (start + end) // 2
    update(node_id * 2 + 1, start, mid, idx, val)
    update(node_id * 2 + 2, mid + 1, end, idx, val)

    tree[node_id] = max(tree[node_id * 2 + 1], tree[node_id * 2 + 2])


N = int(input())
nums = list(map(int, input().split()))
tree = [0] * 4000000 # 4를 곱하면 모든 범위를 커버할 수 있다. 트리는 2의 제곱형태의 길이를 갖는다.

s_nums = [(v, i) for i, v in enumerate(nums)]
s_nums.sort(key = lambda x: (x[0], -x[1])) # val기준으로 정렬, val이 같을 경우 idx 기준으로 정렬한다.

for val, idx in s_nums:
    max_val = find_max_val(0, 0, N - 1, 0, max(idx - 1, 0))
    update(0, 0, N - 1, idx, max_val + 1)

print(tree[0])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬, 세그먼트 트리 이용하여 풀었는데 시간초과가 납니다.

yanghs0540 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말