문제
수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)
출력
A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.
예제 입력 1
5 2
4 1 2 3 5
예제 출력 1
2
풀이
1.
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());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
System.out.println(arr[k-1]);
}2.
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());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
// 1.
quick(arr, 0, n-1, k-1);
System.out.println(arr[k-1]);
}
public static void quick(int[] arr, int s, int e, int k) {
if (s < e){
// 고정 idx를 저장할 변수
// 2.
int pivot = getPivot(arr, s, e);
// pivot인덱스까지는 정렬이 완료 된 상태이므로 k와 일치하면 알고리즘 종료
if (pivot == k) {
return;
// k가 pivot보다 작으면 왼쪽만 정렬
} else if (k < pivot) {
quick(arr, s, pivot - 1, k);
// k가 pivot보다 크면 오른쪽만 정렬
} else {
quick(arr, pivot + 1, e, k);
}
}
}
// 고정idx pivot을 구하는 메서드
public static int getPivot(int[] arr, int s, int e) {
// 만약 남은 idx가 2개면
if (s + 1 == e) {
// 바로 두개의 크기를 비교해서
if (arr[s] > arr[e]) {
// 위치 변경 후
swap(arr, s, e);
}
// 끝 인덱스를 pivot으로 반환
return e;
}
// 중앙 idx를 pivot으로 설정
// 3.
int mid = (s + e) / 2;
swap(arr, s, mid);
// pivot을 구간의 첫idx로 이동
int pivot = arr[s];
// 현구간의 첫 idx
int i = s + 1;
// 현구간의 끝 idx
int j = e;
// 두 idx가 만날때까지 반목문 수행
// 4.
while (i <= j) {
// j는 pivot보다 작은 값을 찾을때가지 왼쪽으로 이동
while (j >= s + 1 && pivot < arr[j]) {
j--;
}
// i는 pivot보다 큰 값을 찾을 때까지 오른쪽으로 이동
while (i <= e && pivot > arr[i]) {
i++;
}
// 인덱스가 아직 교차되지 않았다는 말은
if (i <= j) {
swap(arr, i++, j--);
}
}
// pivot의 인덱스를 원래 위치로 되돌림
// 5.
arr[s] = arr[j];
arr[j] = pivot;
return j;
}
public static void swap(int[] arr, int s, int e) {
int tmp = arr[s];
arr[s] = arr[e];
arr[e] = tmp;
}
리뷰
-
첫번째 풀이로 하니까 퀵정렬이고 뭐고 따로 알고리즘을 짤 필요도 없이 메서드로 풀어졌다;; 근데 제출하고 보니까 제한시간을 겨우 맞추는 상황이었고, 실제로 이걸 의도한 문제는 아닌거 같았다.
-
두번째 풀이가 퀵정렬을 적용한 풀이인데, 알고리즘 원리 자체는 이해하는데 문제가 없었는데, 실제로 코드로 적용시키려고 보니까 처음에 pivot을 제일 왼쪽으로 이동시키고 다시 원래 위치로 이동시키는 부분을 제대로 이해하지 못해 시간이 엄청 걸렸다ㅜㅜ
- main메서드에서 퀵정렬을 호출을 한다.
- 첫 호출에서 pivot을 구하는 getPivot함수를 호출하고,
- 중앙값을 pivot으로 설정한 뒤, 편하게 연산을 하기 위해서 pivot을 제일 왼쪽 인덱스로 이동시킨다.
- 임시로 옮기는 것이고 구간을 나눈 후에 다시 원래 위치로 복구할 것이다.
- i는 pivot보다 큰값을 찾기 위해 왼쪽에서 오른쪽으로 이동하고,
j는 pivot보다 작은 값을 찾기 위해서 오른쪽에서 왼쪽으로 이동한다.- 만약 아직 i와 j가 교차하지 않았다면 i,j의 위치를 서로 바꾸고 다음 루프를 위해 i++, j--를 한다.
if (i <= j) {
swap(arr, i++, j--);
}
이 부분이 헷갈렸는데
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
이거랑 똑같이 동작을 한다. 연산자 위치에 따라 증감연산 순서가 바뀐다는 것은 알고 있었는데 막상 이렇게 되어 있으니 너무 헷갈렸다ㅜㅜ
- 만약 아직 i와 j가 교차하지 않았다면 i,j의 위치를 서로 바꾸고 다음 루프를 위해 i++, j--를 한다.
- i와 j가 서로 교차를 하고 반복문이 끝나면 제일 왼쪽으로 이동시켰던 pivot을 원래 위치로 다시 돌려놓자.
- i와 j가 교차했다는 뜻은, pivot값이 위치할 경계가 나눠졌다는 뜻으로,
i는 pivot보다 큰 첫번째 수의 인덱스를, j는 pivot보다 작은 첫번째 수의 인덱스를 나타내고 있으므로,
j의 위치와 pivot을 임시로 옮겨두었던 맨 왼쪽 인덱스의 위치를 다시 교환해주자. - 만약 3번에서 pivot을 맨 오른쪽으로 옮겼다면 j와 왼쪽인덱스(s)를 교환하는게 아닌
i와 오른쪽인덱스(e)를 교환했을 것이다.
- i와 j가 교차했다는 뜻은, pivot값이 위치할 경계가 나눠졌다는 뜻으로,
- 이렇게 첫 getPivot연산을 통해 pivot보다 작은 값은 왼쪽으로, 큰 값을 오른쪽으로 이동하였다.
- 여기서 오른쪽, 왼쪽 구간 모두 완전히 정렬이 이뤄진 것은 아니고 단순히 pivot을 기준으로 크면 오른쪽, 작으면 왼쪽으로 이동한 상태이다.
이부분도 막상 코드로 보니 헷갈려서 이해하는데 한참 걸렸다ㅜㅜ
- 여기서 오른쪽, 왼쪽 구간 모두 완전히 정렬이 이뤄진 것은 아니고 단순히 pivot을 기준으로 크면 오른쪽, 작으면 왼쪽으로 이동한 상태이다.
- 다시 quick메서드로 돌아와 pivot을 기준으로 k가 더 작다면 왼쪽구간만, 더 크다면 오른쪽 구간만 재귀함수를 진행한다.
이 과정을 통해 전체를 다 정렬하는 것이 아니라 pivot을 기준으로 한쪽 구역만 정렬하면 되기 때문에 시간복잡도 측면에서 유리하다.
알고리즘 자체는 크게 어려운 부분이 없었는데, 막상 재귀함수로 구현해놓은걸 보니까 아득한 기분이 들었다. 진짜 재귀함수 나올 때마다 머리가 터지는 기분이다.... 빨리 이걸 응용할 수 있는 수준까지 오르면 좋겠다ㅜㅜ
꾸준히 하자!