백준 11004번 자바 ☆

문제

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

11004번: K번째 수

1. 처음엔 Arrays.sort를 이용해 쉽게 풀었다. Arrays.sort 의 정렬 방식이 dual pivot quick sort를 사용하기 때문에 가능하다고 판단했고 정답을 맞추긴 했다. 하지만 이번 문제에선 퀵정렬을 사용해 해결하는것이 핵심이었다.

 

2. 퀵정렬 개념자체는 어렵지 않다. pivot을 설정하고 pivot기준 이하 그룹, 이상 그룹으로 나누어 재귀로 배열을 정렬하면 된다. 단순 구현이라면 크게 어렵지 않았지만 해당 문제를 충족하는 코드를 짜는것은 쉽지 않았다.

 

3. 먼저 partition으로 pivot의 인덱스를 구해준다.

첫째, 값의 정렬 상태를 모르기에 중간값을 기준으로 pivot을 정해주고

 

둘째, pivot 값 기준 이상, 이하 그룹을 나누기 쉽게 pivot과 첫번째 값을 swap해준다

.

셋째, 첫 인덱스 left와 끝 인덱스 right를 각각 start와 end에 넣어준다.  이때 left + 1로 넣는 것은 pivot값 바로 다음부터 탐색을 하기 때문이다.

 

넷째, start 와 end의 값을 조건이 충족되는 동안 증감연산자를 통해 값을 변경해준다.

 

다섯째, 변경된 최종 값이 start <= end라면 pivot 기준 이상,이하 그룹이 형성이 안되기 때문에 swap을 통해 값을 바꿔준다.

 

여섯째, while문을 끝낸 start와 end값은 이제 서로 엇갈린 상태이다. 이 때 pivot의 값을 end와 swap해준다. 엇갈린 상태가 되면 일단 pivot기준으로 이상, 이하 그룹이 나눠졌다는 뜻이기 때문이다. 그룹을 나눈 pivot의 인덱스를 반환한다.

 

* if (left + 1 == right)의 조건문은 값의 요소가 2개일 경우 아래의 반복문을 굳이 돌필요없기에 두 값을 비교해 swap을 해주고 right값을 반환해준다.(시간초과방지)

public static int partition(int[] arr, int left, int right) {
		if (left + 1 == right) {
			if (arr[left] > arr[right]) {
				swap(arr, left, right);
			}
			return right;
		}
		
		int mid = (left+right)/2;
		swap(arr, mid, left);
		
		int pivot = arr[left];
		int start = left + 1;
		int end = right;
		
		while (start <= end) {
			while (pivot > arr[start] && start < arr.length-1) {
				start++;
			}
			
			while (pivot < arr[end] && end > 0) {
				end--;
			}
			
			if (start <= end) {
				swap(arr, start++, end--);
			}
		}
		
		arr[left] = arr[end];
		arr[end] = pivot;
		return end;
	}

 

4. partition에서 반환받은 인덱스를 quickSort의 pivot에 넣어 준다. 이 때 pivot인덱스의 값은 정렬을 마친 상태이기 때문에 K-1과 값이 같다면 그대로 메소드를 종료하고 해당 값을 출력한다.

pivot이 K-1보다 작다면 pivot 보다 큰 값들만 정렬해준다. K-1의 위치가 pivot보다 오른쪽이기 때문이다.

pivot이 K-1보다 크다면 반대로 진행해준다.

public static void quickSort(int[] arr, int left, int right, int K) {
		if (left < right) {
			int pivot = partition(arr, left, right);
		
			if (pivot == K-1) {
				return;
			} else if (pivot < K-1) {
				quickSort(arr, pivot+1, right, K);
			} else if (pivot > K-1) {
				quickSort(arr, left, pivot-1, K);
			}
		}
	}

 

5. 전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int K;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		int []arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		quickSort(arr, 0, N-1);
		
		System.out.println(arr[K-1]);
	}
	
	public static void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int pivot = partition(arr, left, right);
		
			if (pivot == K-1) {
				return;
			} else if (pivot < K-1) {
				quickSort(arr, pivot+1, right);
			} else if (pivot > K-1) {
				quickSort(arr, left, pivot-1);
			}
		}
	}
	
	public static int partition(int[] arr, int left, int right) {
		if (left + 1 == right) {
			if (arr[left] > arr[right]) {
				swap(arr, left, right);
                return right;
			}
		}
		
		int mid = (left+right)/2;
		swap(arr, mid, left);
		
		int pivot = arr[left];
		int start = left + 1;
		int end = right;
		
		while (start <= end) {
			while (pivot > arr[start] && start < N-1) {
				start++;
			}
			
			while (pivot < arr[end] && end > 0) {
				end--;
			}
			
			if (start <= end) {
				swap(arr, start++, end--);
			}
		}
		
		arr[left] = arr[end];
		arr[end] = pivot;
		return end;
	}
	
	public static void swap(int[]arr, int first, int second) {
		int temp = arr[first];
		arr[first] = arr[second];
		arr[second] = temp;
	}
}

 

정리 : 퀵소트의 방식이나 단순구현은 어렵지 않게 이해했으나 해당 문제를 푸는 과정에서 많이 헤맸다. 특히 partition을 구현 하는 부분에서 return값을 해당 코드처럼 진행하는지 이해하는데 시간이 오래걸렸다. 그래도 포기하지말고 계속 밀어 붙이자..