글 읽기 - 수열과 쿼리 1 파이썬 질문입니다...

ufshg 2년 전 0

안녕하세요? 많이 고민하다가 부득이하게 질문글 올리게 되었습니다. 도와주시면 감사하겠습니다.

아래처럼 코드를 작성했습니다. 많이 난잡해서 주석 첨부합니다.

알고리즘 상으로 놓친 점은 제가 잘 몰라서 그런지 보이질 않습니다...

아마 트리를 쌓는 과정에서 불필요한 부분들이 있는 것 같은데 파이썬으로 트리를 입력받아 구현하는 예시들은

구글에 검색해도 잘 나오질 않아서 제가 처음으로 구현해 본 것입니다.

파이썬으로 통과를 못하는 문제같진 않아서...

고수분들의 고견을 기다립니다!

import sys
input = sys.stdin.readline
print = sys.stdout.write


# 트리 검색 함수입니다.
def search(node, start, end, k):
    result = 0
    if node:
        # 리프 노드일 경우 카운트
        if node.start == node.end:
            if node.data > k:
                return 1
            else:
                return 0
        else:
            # 노드의 data는 그 노드 아래를 통틀어서 최솟값입니다.
            # 따라서 data값이 k보다 크다면 그 하위의 노드 개수만큼 더해보려고 했습니다.
            if node.data > k:
                return node.end - node.start + 1
            
            # 만약 아니라면 재귀로 호출하게 됩니다.
            
            # 현재 구하고자 하는 범위의 우끝값이 왼쪽 자식의 우끝값보다 작으면 왼쪽만 호출
            if end <= node.left.end:
                result += search(node.left, start, end, k)
            # 반대로 좌끝값이 오른쪽 자식의 좌끝값보다 크면 오른쪽만
            elif start >= node.right.start:
                result += search(node.right, start, end, k)
            # 다 아니면 범위를 반으로 쪼개서 둘 다 호출
            else:
                result += search(node.left, start, node.left.end, k)
                result += search(node.right, node.right.start, end, k)
        return result
    else:
        return 0

# 노드의 구조를 정의했습니다.
class Node:
    def __init__(self, data, start, end):
        self.data = data
        self.start = start
        self.end = end
        self.left = None
        self.right = None

# 완전 이진트리 형태를 만들기 위해 p를 계산해둡니다.
n = int(input())
p = 1
while p < n:
    p *= 2
    
# 수열 전체를 입력받음
A = list(map(int, input().split()))

# B라는 배열을 A 크기만큼 노드를 만들어 채우고 범위를 넘어가면 None으로 채웠습니다.
B = [Node(A[i], i, i) if i < n else None for i in range(p)]

while p:
    p //= 2
    for i in range(p):
        # 순서대로 두개씩 집어서 트리를 쌓아갑니다.
        left, right = B[0 + 2 * i], B[1 + 2 * i]
        # left가 None이 아닌 노드라면
        if left:
            # right도 None이 아닌 노드면
            if right:
                # 그 노드까지의 최솟값을 저장
                B[i] = Node(min(left.data, right.data), left.start, right.end)
                B[i].left, B[i].right = left, right
            else:
                # 오른쪽이 없으니 왼쪽만 저장
                B[i] = Node(left.data, left.start, left.end)
                B[i].left = left
        else:
            # 만약 left right 둘다 None이면 이 칸을 None으로 바꾸고 루프 중지
            B[i] = None
            break
    # p == 1인 경우 root노드까지 완성 되었으므로 빠져나갑니다.
    if p == 1:
        break

s = ""
for _ in range(int(input())):
    start, end, k = map(int, input().split())
    # B[0]이 루트
    s += str(search(B[0], start - 1, end - 1, k)) + '\n'
print(s)

kdyfloat 2년 전 1

a = 2 2 2 2, k = 3

search는 항상 리프까지 내려가기 때문에 범위를 일일이 k와 비교하는 것 보다 비효율적일 수 있습니다.

최대와 최소 트리를 같이 쓰면 그나마 효율적일 것 같습니다만,

a = 2 4 2 4, k = 3 과 같은 경우 결국 리프까지 내려가야 하므로 merge sort tree를 사용하시는게 가장 좋을 것 같네요.

ufshg 2년 전 0

아...! 들어주신 반례를 보고 깨달음을 얻었습니다. 감사합니다 다시한번 해보겠습니다!

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

문제

문제

출처

ICPC

수열과 쿼리 1 파이썬 질문입니다...

ufshg 2년 전 0

kdyfloat 2년 전 1

ufshg 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말