![[백준,BOJ 2751] 수 정렬하기 2( JAVA 구현, 재풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbW5BAE%2FbtqLq4pPXiW%2FwGlezJC1XAP3ESKLBsHZk1%2Fimg.png)
반응형
-내 생각
이전에 퀵 소트를 이용한 풀이를 작성한 적이 있는데, 문제가 수정된 건지 아니면 테스트 케이스가 바뀐 것인지 모르겠지만, 다시 제출해보니 오답처리를 받았다. 따라서 문제 설명에서 제시하는 O(nlogn) 시간 복잡도를 가지고 있는 정렬들을 이용해 다시 풀어보고자 했다.
-해법
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main{
static int sorted[];
// i: 정렬된 왼쪽 리스트에 대한 인덱스
// j: 정렬된 오른쪽 리스트에 대한 인덱스
// k: 정렬될 리스트에 대한 인덱스
/* 2개의 인접한 배열 list[left...mid]와 list[mid+1...right]의 합병 과정 */
static void merge(int[] arr, int left, int mid, int right) {
int i, j, k, l;
i = left;
j = mid + 1;
k = left;
// 왼쪽 리스트 배열과 오른쪽 리스트 배열을 비교해 정렬하며 임시배열에 저장한다.
while(i<=mid && j<=right) {
if(arr[i]<=arr[j])
sorted[k++] = arr[i++];
else
sorted[k++] = arr[j++];
}
// 남아 있는 값들을 일괄 복사
if(i>mid){
for(l=j; l<=right; l++)
sorted[k++] = arr[l];
}
// 남아 있는 값들을 일괄 복사
else{
for(l=i; l<=mid; l++)
sorted[k++] = arr[l];
}
// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
for(l=left; l<=right; l++){
arr[l] = sorted[l];
}
}
static void merge_sort(int[] arr,int left, int right) {
int mid; // 중간 위치 인덱스 저장 변수
if(left<right) { // 분할이 가능하다면
mid = (left+right)/2; // 중간 위치 인덱스 저장
merge_sort(arr,left,mid); // 앞쪽 부분 리스트 정렬
merge_sort(arr,mid+1,right); // 뒤쪽 부분 리스트 정렬
merge(arr,left,mid,right); // 정렬된 2개의 부분 배열을 병합
}
}
public static void main(String[] args) throws IOException{
// 데이터의 수가 100만이기 때문에 입, 출력 역시 신경써 주어야 한다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int arr[] = new int[n]; // 실제 데이터가 정렬 될 배열
sorted = new int[n]; // 정렬을 위해 임시로 사용할 배열, 마찬가지로 정렬 때 마다 배열을 할당 시 시간초과/ 정적변수로 한 번만 할당한다.
for(int i=0;i<arr.length;i++) {
arr[i] = Integer.parseInt(br.readLine());
}
merge_sort(arr,0,arr.length-1); // 병합정렬 시작
for(int i=0;i<arr.length;i++) {
bw.write(String.valueOf(arr[i])+"\n"); // 출력
}
bw.flush();
bw.close();
}
}이 문제 자체로 주의해야 하는 점은 데이터의 수가 100만 개까지 가능하기 때문에 입, 출력을 신경 써 주어야 한다.
병합 정렬을 사용할 경우는 정렬 때 사용하는 임시 배열을 미리 정적 변수로 선언한 뒤, 한 번만 메모리를 할당해야 한다.
이후에 병합정렬 알고리즘을 사용하면 된다.
--------- 힙 정렬 추가 예정 --------------
병합정렬과 함께 O(NlogN) 시간 복잡도를 가지는 힙 정렬은 완전 이진트리의 한 종류로써 부모 노드가 자식 노드들 보다 큰 값을 가지는 '최대 힙'과 부모 노드가 자식 노드들 보다 작은 값을 가지는 '최소 힙' 두 종류가 존재하며 이러한 특성으로 여러 개의 수 중 최댓값과 최솟값을 찾는 데 특화되어 있는 자료구조이다. 이 문제 풀이에는 최대 힙을 사용하였다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Main {
public static void heapify(int[] arr,int size, int i) { // 최대 힙 구성, 자료 배열과 크기 노드를 전달한다.
int parent = i; // 전달받은 노드가 부모 노드로 저장
int lchild = (i * 2) + 1; // 부모 노드의 왼쪽 자식 노드
int rchild = (i * 2) + 2; // 부모 노드의 오른쪽 자식 노드
/*
완전 이진트리의 한 종류인 힙은 완전 이진트리의 특성을 그대로 따르므로
왼쪽 자식노드부터 차례대로 노드들이 채워진다는 특성이 있다.
*/
// 그러므로 왼쪽 자식노드가 완전이진트리의 크기를 벗어나지 않으면서, 크기가 크다면 교환한다.
if(size > lchild && arr[parent] < arr[lchild]) {
parent = lchild;
}
/* 만약, 왼쪽 자식노드가 부모노드와 교환되었다면, 현재 parent에는 왼쪽 자식노드의 인덱스가 저장되어 있다.
이후 조건문을 만나면 사실상 왼쪽 자식노드와 오른쪽 자식노드의 크기를 비교한다.
즉, 왼쪽과 오른쪽 자식노드 중 큰 값을 가지는 자식노드를 찾는 과정이다.
*/
if(size > rchild && arr[parent] < arr[rchild]) {
parent = rchild;
}
if(parent != i) { // 기존의 전달받은 부모노드의 값이 변하였다면, 교환이 발생해야 한다.
// 왼쪽 또는 오른쪽 자식노드와 전달받은 부모노드의 값을 교환한다.
int temp = arr[parent];
arr[parent] = arr[i];
arr[i] = temp;
// 교환한 뒤 아래쪽 이진트리에서도 최대힙을 다시 구성해야 하므로 재귀호출한다.
heapify(arr, size, parent);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int arr[] = new int[n];
for(int i=0;i<arr.length;i++) { // 데이터 입력
arr[i] = Integer.parseInt(br.readLine());
}
for(int i = (arr.length/2)-1;i>=0;i--) { // 힙의 중간부터 부모노드로써 전달, 잎새노드는 자식이 존재하지 않으므로 고려할 필요가 없다.
heapify(arr,arr.length,i);
}
for(int i = arr.length-1;i>=0;i--) { // 한 번 최대 힙이 구성되었으므로,
int temp = arr[0]; // 최대 값과 첫 번째 값을 교환한다.
arr[0] = arr[i];
arr[i] = temp;
// 힙의 크기를 줄여가며 다시 최대 힙을 구성한 뒤, 첫 번째 값과 교환을 반복한다.
// 이 때는 루트 노드부터 탐색한다. 최댓값과 루트노드가 교환 과정이 이루어졌기 때문이다.
heapify(arr,i,0);
}
for(int i=0;i<arr.length;i++) { // 정렬완료 된 값을 출력
bw.write(String.valueOf(arr[i])+"\n");
}
bw.flush();
bw.close();
}
}코드 자체는 어려울 것이 없지만, 처음에 힙 정렬을 공부하는 과정에서 복잡하게 느껴진 부분이 많았다. 이 문제를 풀기 위해서는 완전이진트리의 특성과 최대 힙, 최소 힙의 구분이 가능하여야 하며 코드 작성 과정에서는 최대 힙을 먼저 한 번 구성한 뒤, 크기를 줄여가며 최대 힙을 구성해야 한다는 점을 명심한다면 어렵지 않게 풀 수 있을 것이라 생각된다.
반응형