[백준] 2751. 수 정렬하기2 - JAVA

문제

 

---

풀이

 

힙정렬 O(nlog n)

힙정렬은 완전이진트리를 배열로 표현한 힙 구조를 이용해 정렬하는 알고리즘으로,

아래 그림과 같이 배열을 이진트리로 나타내야한다.

이진트리의 가장 중요한 개념은

부모가 n 이라면

왼쪽 자식은 n*2+1

오른쪽 자식은 n*2+2 라는 점을 알고 시작하면 좋다.

 

필요한 메서드

1. swap()

⤷ int A 와 int B가 있다고 가정, A와 B의 값 서로 바꾸기

 

2. heapify()

⤷ while 문을 통해서 부모 ↔ 자식 사이의 값 비교 후 더 크거나 더 작은 수 선택해서 자리 바꾸기

더 이상 자식이 없거나, 기존 최대힙 or 최소힙 이라면 while문 종료

 

3. heapsort()

⤷ 힙정렬을 위한 메서드 heapify() + swap() 을 사용

우선, 최대힙으로 만들어 주기

다음으로 루트와 마지막 숫자와 자리 바꾼 후 다시 자리 찾아가기 반복

 

---

코드

 

import java.io.*;

 

public class Main{

    //스왑

    public static void swap(int[] a, int i, int largest){

        int t = a[i];

        a[i] = a[largest];

        a[largest] = t;

    }

    //부모랑 자식 비교

    public static void heapify(int[] a, int n, int i){

        while(true){

            int largest = i;

            int left = i*2+1;

            int right = i*2+2;

            if(left<n && a[left]>a[largest]){largest = left;}

            if(right<n && a[right]>a[largest]){largest = right;}

            if(largest==i){break;}

            swap(a,largest,i);

            i=largest;

        }

    }

 

    //힙정렬

    public static void heapsort(int[] a){

        int n = a.length;

        //최대힙만들기

        for(int i=n/2-1; i>=0; i--){

            heapify(a,n,i);

        }

 

        //루트 맨뒤로 보내고 재정렬하기

        for(int end=n-1; end>0; end--){

            swap(a,end,0);

            heapify(a,end,0);

        }

    }

 

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(

            new InputStreamReader(System.in));

        PrintWriter pw = new PrintWriter(System.out);

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        for(int i=0; i<N; i++){

            arr[i] = Integer.parseInt(br.readLine());

        }

        heapsort(arr);

 

        //출력하기

        for(int i=0; i<N; i++){

            pw.println(arr[i]);

        }

        pw.flush();

        pw.close();

        br.close();

    }

   

}