JAVA 자료구조 : 최소 힙[백준 1927]

스터디사이트 : https://www.acmicpc.net/

JAVA 자료구조 : 최소 힙[백준 1927]

※ 문제 Url
    https://www.acmicpc.net/problem/1927

※ 해결법

힙정렬 중 최소힙을 이용함 : https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC

※ 문제이해

힙정렬에 대해 위의 위키백과 링크에 힙정렬에 대한 C언어 코드 설명이 나와있는데, 그것 보고 이해했다.

완전이진트리

끝 부분(마지막 레벨)을 제외하고 모든 노드가 채워진(마지막 레벨을 제외하고는 모든 노드가 자식노드를 2개를 가진) 이진 트리. 

마지막 레벨의 노드들은 왼쪽으로 채워져 있다. 

마지막 레벨이 다 채워질 수도 있다.

부모노드 자리수와 자식노드(좌,우)자리수 구하는 공식 (인덱스 시작이 0이라 할 때)

부모노드 : (총노드수 / 2)

자식노드(좌) : (부모노드 x 2) + 1

자식노드(우) : (부모노드 x 2) + 2

힙정렬

내림차순 정렬을 위해서는 최대 힙을 구성

오름차순 정렬을 위해서는 최소 힙을 구성

완전이진트리를 구성시킨다.

힙정렬 > 최소 힙

완전이진트리 구성할때, 부모와 자식노드 좌, 우가 있으면, 부모노드의 값이 자식노드보다 작아야 한다

최소 힙정렬 수행방법

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.

2. 완전이진트리의 부모,자식으로 구성된 트리그룹(노랑색 표시)을 가장 아래부터 루트까지 훑어가며 최소힙의 취지에 맞게 순차적으로 데이터를 넣는다.

3. 루트노드의 숫자는 가장 작은 수가 될 것이니, 루트노드를 정렬배열의 인덱스 [0]부터 추가한다.

4. 가장 작은 수(루트에 위치)를 가장 큰 수와 교환시키고, 이진트리의 인덱스길이를 하나 줄인다. 왜냐면 맨 마지막 인덱스는 배열에 들어가있으니까..

4. 2~4단계를 반복한다.

※ 후기

첨에는 LinkedList를 직접 코딩해서 풀어봤는데, 백준홈피에서는 항상 시간초과가 떴다.

그래서 int배열만을 이용해서 풀었다.

위키백과에 있는 힙정렬의 코드를 참조해서 개념을 탑재한것 같다 ㅋ

※ 내가 푼 코드

태클 얼마든지 환영합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    int[] heapArr;  // 전역변수는 자동으로 initialize 된다.
    
    public static void main(String[] args) throws IOException {
        new Main();
    }
    
    Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // Line 1
        int N = Integer.parseInt(br.readLine());
        if(N%2==1){    // Heap정렬 완전이진트리 구성.
            heapArr = new int[N];
        }else{
            heapArr = new int[N+1];
        }
        
        int i=0;    // Heap배열의 길이
        // 입력값 배열로 넣음.
        // 입력값이 0이면: 최소힙노드의 Root값 출력 + 현재 배열에 0이 아닌 수 재정렬 + 최소힙노드삽입
        // 입력값이 0이 아니면: 현재 배열에 0이 아닌 수 재정렬 + 최소힙노드삽입
        while(N-->0){
            int valueN = Integer.parseInt(br.readLine());
            if(valueN > 0) {
                // 최소힙 삽입 후 정렬 수행.
                heapArr[i] = valueN;
                i++;
                for(int j=(i-1)/2; j>=0; j--) {
                    sortHeap(j, i);     // {4, 3, 2, 1, 0}
                }
                
            }else{
                i--;
                if(i<0){
                    i=0;
                    sb.append("0\n");
                    continue;
                }
                // 루트노드 제외 & 배열크기 줄임
                sb.append(heapArr[0] + "\n");
                swapArr(0, i);
                for(int j=(i-1)/2; j>=0; j--){
                    sortHeap(j, i);
                }
            }
        } //end while
        System.out.println(sb.toString());
    }
    
    // 힙배열에 데이터 추가
    void sortHeap(int cur, int nodeQty){
        while(cur < nodeQty){
            int leftIndex=(cur*2) + 1;
            int rightIndex=(cur*2) + 2;
            int pointer;  // 힙배열 포인터
            // nodeQty가 9라면 node가 9개인데, node[9]는 존재할 수 없으므로 '=' 넣음
            if(leftIndex >= nodeQty && rightIndex >= nodeQty)   break;  // 자식 인덱스가 노드 인덱스보다 많을 수 없다.
 
            pointer = cur;  // 이 공식이 다음 if문을 거치고 나서도 true라면, 해당 루트노드는 정렬이 다 끝난 것.
 
            // 좌측노드, 우측노드 중 하나가 없을 수도 있는 부분을 체크하는 로직.
            if(leftIndex < nodeQty && heapArr[pointer] > heapArr[leftIndex]){
                pointer = leftIndex;
            }
            if(rightIndex < nodeQty && heapArr[pointer] > heapArr[rightIndex]){
                pointer = rightIndex;
            }
            if(cur==pointer)    break;
 
            swapArr(cur, pointer);  // 부모, 좌/우 자식노드들 중 제일 작은 값이 부모노드로 가게 위치변환
            cur = pointer;
        }
    }
    
    void swapArr(int cur, int pointer){
        int temp=0;     // 배열 swap을 위한 임시변수
        temp = heapArr[cur];
        heapArr[cur] = heapArr[pointer];
        heapArr[pointer] = temp;
    }
}