문제
https://www.acmicpc.net/problem/11650
풀이
이 문제는 정렬에 사용되는 기준이 두개가 존재한다. 정렬 조건은 다음과 같다.
- x좌표를 기준으로 오름차순으로 정렬.
- x좌표가 동일할 경우 y좌표를 기준으로 오름차순 정렬.
먼저 맨처음에는 한번의 정렬로 두 기준을 만족하는 정렬 알고리즘을 구현하려고 했으나 쉬운일이 아니였다.
퀵정렬을 활용해 복수조건을 적용하여 정렬을 하고싶었으나 정상적으로 정렬이 되지 않는것을 확인후 검색을 했다.
여기서 안정 정렬, 불안정 정렬에 대한 개념을 접하게 된다.
안정 정렬 vs 불안정 정렬
안정 정렬
중복되는 값에 대해서 원래의 순서를 유지하여 정렬을 진행
복수기준을 이용해 정렬시 전 기준에 대한 순서를 유지한체 정렬이 이루어짐
불안정 정렬
중복되는 값에 대해 원래 배열 순서를 보장하지 못함
복수기준을 정렬시 전 기준에 대해 정렬된 내용에 영향을 주게 되어 정상적인 정렬이 이루어지지 못함.
큇정렬(Quick Sort)는 불안정 정렬에 속했기때문에 복수조건을 적용할수도 각각 기준을 적용해 정렬을 두번을 돌려도 원하는 값을 얻어낼 수 없었다.
따라서 복수조건을 이용해 정렬을 한번진행하든, 각 조건을 이용해 정렬을 두번을 적용해든 안정 정렬이 무조건 활용 되어야만 했다.
맨 처음에 복수조건에 대해서도 전기준에 대한 순서가 유지 된다는 점을 모른 체로 1차적으로 퀵정렬을 활용해 y좌표 기준을 정렬한 다음 안정 정렬인 병합 정렬을 이용해 최종적인 값을 얻도록 하였으나 시간 초과가 발생하였다.
사실 위 사실을 문제풀이를 성공하기까지 알지 못하고 더 빠른 정렬 방법을 찾는데만 집중했다.
결국 자바의 기본 배열 정렬 매소드로 y좌표에 대해 1차정렬 하고 다시 병합정렬(Merge Sort)을 진행하도록하였다.
(자바의 배열 기본 정렬 매소드는 퀵 정렬을 개량해 더 빠른 듀얼 피벗 퀵 정렬(Dual Pivot Quick Sort)을 활용함)
정답이긴 하나 걸린 시간을 보면 오버되었으나 오차범위 내로 간신히 통과한것을 확인할 수 있다.
그래서 병합정렬에 복수 조건을 활용하여 한번의 정렬만 하는 코드로 다시 진행하였다.
200ms나 시간단축에 성공하였다.👍
코드
두번 정렬 진행 (1차 시도)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Arrays;
public class Main
{
static int[][] arr = new int[100002][2];
static void mergeSortTask(int start, int end, int unit) {
int groupEa = (int) ((end-start+1)/unit) + ((end-start+1)%unit != 0 ? 1:0);
int[][] tempArr = new int[100002][2];
for(int i=0; i<(groupEa-(groupEa%2)); i+=2) { // 짝이 지어지는 그룹끼리 먼저 정렬
int[] groupA = {i*unit,(i+1)*unit-1}, groupB = {(i+1)*unit,(i+2)*unit-1 > end ? end : (i+2)*unit-1}; // {startIdx, endIdx}
int lengthA = groupA[1]-groupA[0]+1, lengthB = groupB[1] - groupB[0]+1;
int cursor = groupA[0], cursorA=groupA[0],cursorB=groupB[0];
for(int j=0; j<lengthA+lengthB+1; j+=1) {
if(cursorA > groupA[1]) {
tempArr[cursor] = arr[cursorB];
cursorB += 1;
cursor+=1;
continue;
}
if(cursorB > groupB[1]) {
tempArr[cursor] = arr[cursorA];
cursorA += 1;
cursor+=1;
continue;
}
//단일 조건
if(arr[cursorA][0] > arr[cursorB][0]) {
tempArr[cursor] = arr[cursorB];
cursorB +=1;
}else {
tempArr[cursor] = arr[cursorA];
cursorA +=1;
}
cursor+=1;
}
}
if(groupEa%2 == 1) for(int i=unit*(groupEa-1); i<=end; i+=1) {tempArr[i] = arr[i];}
arr = tempArr;
if(unit*2 < end-start+1) mergeSortTask(start,end,unit*2);
}
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());
for(int i=0; i<n; i+=1) {
String[] input = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(input[0]);
arr[i][1] = Integer.parseInt(input[1]);
}
//자바 내부 정렬 매소드(Dual Pivot Quick Sort)
Arrays.sort(arr,0,n, (o1,o2)->{
return o1[1]-o2[1];
});
// 직접 만든 병합 정렬 매소드
mergeSortTask(0,n-1,1);
for(int i=0; i<n; i+=1) {
bw.write(Integer.toString(arr[i][0]) + " " + Integer.toString(arr[i][1])+"\n");
}
bw.flush();
bw.close();
}
}
복수조건 활용 한번만 정렬 (최종 시도)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class Main
{
static int[][] arr = new int[100002][2];
static void mergeSortTask(int start, int end, int unit) {
int groupEa = (int) ((end-start+1)/unit) + ((end-start+1)%unit != 0 ? 1:0);
int[][] tempArr = new int[100002][2];
for(int i=0; i<(groupEa-(groupEa%2)); i+=2) { // 짝이 지어지는 그룹끼리 먼저 정렬
int[] groupA = {i*unit,(i+1)*unit-1}, groupB = {(i+1)*unit,(i+2)*unit-1 > end ? end : (i+2)*unit-1}; // {startIdx, endIdx}
int lengthA = groupA[1]-groupA[0]+1, lengthB = groupB[1] - groupB[0]+1;
int cursor = groupA[0], cursorA=groupA[0],cursorB=groupB[0];
for(int j=0; j<lengthA+lengthB+1; j+=1) {
if(cursorA > groupA[1]) {
tempArr[cursor] = arr[cursorB];
cursorB += 1;
cursor+=1;
continue;
}
if(cursorB > groupB[1]) {
tempArr[cursor] = arr[cursorA];
cursorA += 1;
cursor+=1;
continue;
}
// 복수 조건을 활용하여 정렬
if(arr[cursorA][0] > arr[cursorB][0] || (arr[cursorA][0] == arr[cursorB][0] && arr[cursorA][1] > arr[cursorB][1])) {
tempArr[cursor] = arr[cursorB];
cursorB +=1;
}else {
tempArr[cursor] = arr[cursorA];
cursorA +=1;
}
cursor+=1;
}
}
if(groupEa%2 == 1) for(int i=unit*(groupEa-1); i<=end; i+=1) {tempArr[i] = arr[i];}
arr = tempArr;
if(unit*2 < end-start+1) mergeSortTask(start,end,unit*2);
}
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());
for(int i=0; i<n; i+=1) {
String[] input = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(input[0]);
arr[i][1] = Integer.parseInt(input[1]);
}
// 하나의 정렬 매소드만 활용
mergeSortTask(0,n-1,1);
for(int i=0; i<n; i+=1) {
bw.write(Integer.toString(arr[i][0]) + " " + Integer.toString(arr[i][1])+"\n");
}
bw.flush();
bw.close();
}
}
연관 게시물
퀵 정렬 - <url 첨부 예정>
병합 정렬 - https://hoshi2710.github.io/algorithm/Algorithm-MergeSort.html
[유사 문제] 10814 나이순 정렬 - <url 첨부 예정>
