[백준/Python] 11286번 - 절댓값 힙

 

문제

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

 

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

 

 

입력

 

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.

 

만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.

 

입력되는 정수는 -2^31보다 크고, 2^31보다 작다.

 

 

출력

 

입력에서 0이 주어진 회수만큼 답을 출력한다.

 

만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

 

풀이

 

최소 힙의 구조에 조건이 추가 된 형태의 문제이다.

 

최대 힙과 마찬가지로 완전 이진트리의 구조이기 때문에 [부모노드의 index]*2가 왼쪽 자식 노드의 index값이며 [부모노드의 index]*2+1는 오른쪽 자식 노드의 index값이다.

​

1. 노드의 삽입 시

• 완전 이진 트리의 마지막 index 다음 index에 삽입하고 부모노드와 값을 비교한 뒤 더 작으면 교환하고, 크면 그대로 둔다.

2. 노드의 삭제 시

• 노드를 삭제하고 자식 중 마지막 index를 삭제한 노드의 index 위치로 옮긴다. 그리고 왼쪽 자식 노드와 오른쪽 자식 노드 중 작은 값과 값을 비교하고 자식 노드가 더 작면 위치를 교환한다.
• 이때, 만약 오른쪽 자식과 왼쪽 자식의 절댓값이 같다면 실수 값을 비교해서 더 작은 값을 선택한다.
• 만약 자식 노드와 비교했을 때, 현재 노드값과 절댓값이 같다면 실수 값을 비교해서 더 현재 노드의 값이 더 크다면 위치를 교환하고 같다면 그대로 둔다.
• 만약 현재 노드의 값이 더 작다면 break하면 된다.
• 위 과정을 반복하면 된다.

 

 

Code

 

 

import sys
input=sys.stdin.readline
index=0
lst=[0]*200002
for _ in range(int(input())):
    N=int(input())
    if N==0:
        print(lst[1])
        lst[1],lst[index]=lst[index],0
        if index:
            index-=1
        ca_idx=1
        while True:
            ca_idx_2=ca_idx*2
            if lst[ca_idx_2]==0:
                break
            else:
                if lst[ca_idx_2+1]==0:
                    if abs(lst[ca_idx])>abs(lst[ca_idx_2]):
                        lst[ca_idx_2],lst[ca_idx]=lst[ca_idx],lst[ca_idx_2]
                        ca_idx *= 2
                    elif abs(lst[ca_idx])==abs(lst[ca_idx_2]):
                        if lst[ca_idx]>lst[ca_idx_2]:
                            lst[ca_idx_2], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2]
                            ca_idx *= 2
                        else:
                            break
                    else:
                        break
                else:
                    if abs(lst[ca_idx_2])<abs(lst[ca_idx_2+1]):
                        if abs(lst[ca_idx]) > abs(lst[ca_idx_2]):
                            lst[ca_idx_2], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2]
                            ca_idx *= 2
                        elif abs(lst[ca_idx]) == abs(lst[ca_idx_2]):
                            if lst[ca_idx] > lst[ca_idx_2]:
                                lst[ca_idx_2], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2]
                                ca_idx *= 2
                            else:
                                break
                        else:
                            break

                    elif abs(lst[ca_idx_2])==abs(lst[ca_idx_2+1]):
                        if lst[ca_idx_2]<lst[ca_idx_2+1]:
                            if abs(lst[ca_idx]) > abs(lst[ca_idx_2]):
                                lst[ca_idx_2], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2]
                                ca_idx *= 2
                            elif abs(lst[ca_idx]) == abs(lst[ca_idx_2]):
                                if lst[ca_idx] > lst[ca_idx_2]:
                                    lst[ca_idx_2], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2]
                                    ca_idx *= 2
                                else:
                                    break
                            else:
                                break
                        else:
                            if abs(lst[ca_idx]) > abs(lst[ca_idx_2+1]):
                                lst[ca_idx_2+1], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2+1]
                                ca_idx = ca_idx*2+1
                            elif abs(lst[ca_idx]) == abs(lst[ca_idx_2+1]):
                                if lst[ca_idx] > lst[ca_idx_2+1]:
                                    lst[ca_idx_2+1], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2+1]
                                    ca_idx = ca_idx * 2 + 1
                                else:
                                    break
                            else:
                                break
                    else:
                        if abs(lst[ca_idx]) > abs(lst[ca_idx_2 + 1]):
                            lst[ca_idx_2 + 1], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2 + 1]
                            ca_idx = ca_idx * 2 + 1
                        elif abs(lst[ca_idx]) == abs(lst[ca_idx_2 + 1]):
                            if lst[ca_idx] > lst[ca_idx_2 + 1]:
                                lst[ca_idx_2 + 1], lst[ca_idx] = lst[ca_idx], lst[ca_idx_2 + 1]
                                ca_idx = ca_idx * 2 + 1
                            else:
                                break
                        else:
                            break

    else:
        index+=1
        lst[index]=N
        ca_idx=index
        while ca_idx>1:
            ca_idx_2=ca_idx//2
            if abs(lst[ca_idx])<abs(lst[ca_idx_2]):
                lst[ca_idx],lst[ca_idx_2]=lst[ca_idx_2],lst[ca_idx]
                ca_idx=ca_idx_2
            elif abs(lst[ca_idx])==abs(lst[ca_idx_2]):
                if lst[ca_idx]<lst[ca_idx_2]:
                    lst[ca_idx], lst[ca_idx_2] = lst[ca_idx_2], lst[ca_idx]
                    ca_idx = ca_idx_2
                else:
                    break
            else:
                break

 

---

 

이렇게 코드가 길어질 문제였나...??

 

 

 

11286번: 절댓값 힙