[백준/자바]11004 K번째 수 구하기

[백준/자바]11004 K번째 수 구하기 

📌 문제 

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

 

 

📣 출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

 

 

 

---

 

 

 

💎 문제분석하기

 

이 문제는 퀵정렬로 풀고자 하기에 먼저 퀵정렬에 대한 이해가 필요했다. 

 

따라서 먼저 퀵정렬을 이해하고 이 문제를 풀이하였다. 

 

퀵정렬은 기준값(Pivot)을 정한 뒤 해당 값을 기준으로 작은 값, 큰값을 분류하여 반복함으로써 정렬을 하는 알고리즘이다. 

 

먼저 한 pivot을 정한뒤 데이터를 두 집합으로 나누어 정렬한다. 

 

로직 자체는 P를 정하고, 그것을 제외한 나머지 숫자가 양 끝단에서부터 시작해서 

1) 오른쪽은 P보다 작으면

2) 왼쪽은 P보다 크면 

바꿔주는 작업을 반복하다가 

두 지점이 만나면 p랑 교환을 한다.

 

그리고 이 다음부터는 양 집단으로 나뉜 두 집단에서 같은 작업을 반복하다보면 정렬이 완료된다. 

 

처음 접했을 때 이해가 안돼서 손으로 쓰면서 이해해보았다. 

 

 

 

자료 참고 : https://mygumi.tistory.com/308

 

 

코드 구현은

main부 

quicksort 실행부 

partion부 (퀵정렬 메인 알고리즘)

swap기능부 

로 나뉜다. 

 

quickSort 함수부분은 재귀적으로(스스로를 호출하여) 진행이 된다. 

 

사실상 파티션부가 핵심이고, 지정 위치를 다르게 해줄 수 있는 부분이다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];

		for (int i = 0; i < N; i++)
			A[i] = Integer.parseInt(br.readLine());

		quickSort(A, 0, N-1);

		// 출력부
		StringBuilder sbAnswer = new StringBuilder();
		for (int number : A) {
			sbAnswer.append(number).append("\n");
		}
		System.out.println(sbAnswer);

	}

	public static void quickSort(int[] array, int L, int R) {
		if (L >= R) { return; }
		int pi = partition(array, L, R);

		quickSort(array, L, pi - 1);
		quickSort(array, pi + 1, R);
	}

	public static int partition(int[] array, int L, int R) {
		int mid = (L + R) / 2;
		swap(array, mid, L);

		int pivot = array[L];
		int i = L;
		int j = R;

		while (i < j) {
			while (pivot < array[j]) {
				j--;
			}

			while (i < j && pivot >= array[i]) {
				i++;
			}
			swap(array, i, j);
		}
		array[L] = array[i];
		array[i] = pivot;
		return i;
	}

	private static void swap(int[] arr, int L, int R) {
		int temp = arr[L];
		arr[L] = arr[R];
		arr[R] = temp;
	}
}

 

 

퀵 정렬의 기본 알고리즘이다. 

 

 

이 문제에 적용하면 마지막 부분에서 A[k-1]로 구하면 답이 된다.

 

하지만 퀵정렬의 특성상 최악의 경우를 고려한다면 시간복잡도가 O(n^2)으로 상승할 것이므로, k 값을 고려해서 최선의 피벗을 선택해주는 방법을 생각해볼 수 있다. 

 

먼저 파티션을 1회 진행했다고 치고 pivot이 리턴된 상황을 생각해보면, 

 

pivot을 기준으로 왼쪽은 무조건 작은 수들이 존재하고 오른쪽은 큰수들이 존재한다. 

 

따라서, 

 

1) pivot == 구해야 하는 수 k인 경우, 더 이상의 알고리즘을 진행하지 않아도 된다.  

2) pivot이 구해야 하는 수 k보다 큰 경우, 즉 k가 왼쪽에 있으므로 오른쪽은 더이상 정렬하지 않아도 된다.

3) pivot이 구해야 하는 수 k보다 작은 경우, 즉 k가 오른쪽에 있으므로 오른쪽 그룹만 정렬하면 된다. 

 

 

 

 

 

💡 코드 구현하기

 

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

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] array = new int[N];

		for (int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken());

		quickSort(array, 0, N-1, K-1);

		// 출력부
		System.out.println(array[K-1]);
	}

	public static void quickSort(int[] array, int L, int R, int K) {

		if (L >= R) { return; }
		int pivot = partition(array, L, R);

		if (pivot == K) { return; }
		else if (K < pivot) {
			quickSort(array, L, pivot - 1, K);
		} else {
			quickSort(array, pivot + 1, R, K);
		}

	}

	public static int partition(int[] array, int L, int R) {
		int mid = (L + R) / 2;
		swap(array, mid, L);

		int pivot = array[L];
		int i = L;
		int j = R;

		while (i < j) {
			while (pivot < array[j]) {
				j--;
			}

			while (i < j && pivot >= array[i]) {
				i++;
			}
			swap(array, i, j);
		}
		array[L] = array[i];
		array[i] = pivot;

		int newPivot = i;
		return newPivot;
	}

	private static void swap(int[] arr, int L, int R) {
		int temp = arr[L];
		arr[L] = arr[R];
		arr[R] = temp;
	}
}

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편