https://www.acmicpc.net/problem/11004
요새 알고리즘 코딩테스트 책을 사서 공부하고 있다. (오타 개많다 사지마라)
하도 오타가 많고 설명이 그렇게 친절하다고 느껴지진 않는다. 천재들은 왜 죄다 설명을 요약하는거냐?
그래서 책 안보고 풀었더니 인텔리제이에선 정답은 맞게 뜨는데 오답이라고 떴다. 왜일까?
오답코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
for(int i=0; i<n; i++){
if(k==i){
System.out.println(arr[i-1]);
}
}
}
}그래서 약간 수정을 해서 제출 했더니 정답처리 되었다.
정답코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
System.out.println(arr[k-1]);
}
}for문이랑 if문을 지웠다. 간단하게 생각하면 되는건데 등신같이 더 복잡하게 생각했다. 결국 BufferedReader,StringTokenizer,Arrays.sort() 를 써서 해결했지만 그다지 효율적이진 않다.
어디서 주워들은 바로는 Arrays.sort()가 더블 어쩌고 정렬을 사용한다고 한다.
Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용한다고 했다. 물론 평균 시간복잡도가 O(nlogn) 이고 매우 빠른 알고리즘인 것은 맞다. 그러나 최악의 경우 시간복잡도는 O(n2) 이라는 점을 기억해야한다.
출처 : https://st-lab.tistory.com/106
이 분은 뭐하는 분일까? 모르는게 없다. 티스토리계의 위키백과다
저 블로그 글을 보면 Collections.sort()를 쓰면 된다고 한다
Collections.sort() 은 Timsort이다. Timsort 의 경우 합병 및 삽입정렬 알고리즘을 사용한다. 이렇게 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm 이라고 하는데, 합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn) 을 보장하고. 삽입정렬(Insertion sort)의 경우 최선의 경우는 O(n) , 최악의 경우는 O(n2) 이다. 그리고 두 정렬 모두 안정 정렬(stable sort)이기 때문에 Timsort를 hybrid stable sorting algorithm이라고도 한다.
즉, 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort 라는 것이다. 실제로 파이썬이나 기타 정렬 알고리즘에서 가장 많이 쓰이는 알고리즘이기도 하다.
시간복잡도 O(n) ~ O(nlogn) 을 보장한다는 장점이 있다. 대신에 Collections.sort()를 사용하고자 한다면 가장 쉬운 방법으로는 일반적인 primitive 배열이 아닌 List 계열(ArrayList, LinkedList 등..)의 자료구조를 사용하여 정렬해야한다.
이 문제는 퀵 정렬을 사용해서 풀어야한다해서 블로그를 참고해서 코드를 짰더니 시간 초과가 났다. 졸라 힘들게 이해(는 못했고 외움)해서 코드 짰더니 틀렸다니까 살짝 짜증이 났다. 근데 떠먹여줘도 응용을 못하는 내 잘못이지 ㅎ
퀵 정렬(왼쪽 기준)을 사용한 문제 풀이(오답)
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());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
pivot_sort(arr,0,arr.length-1);
System.out.println(arr[k-1]);
}
private static void pivot_sort(int[] arr, int lo, int hi) {
// 정렬할 원소가 1개 이하기 때문에 정렬하지 않고 함수 종료한다
if(lo>=hi) return;
int pivot = partition(arr,lo,hi);
// 재귀(리커시브)
pivot_sort(arr,lo,pivot-1);
pivot_sort(arr,pivot+1,hi);
}
private static int partition(int[] arr, int left, int right) {
int lo = left;
int hi = right;
int pivot = arr[left];
// lo가 hi 보다 작을 때 까지 반복한다
while(lo < hi){
// 배열 오른쪽이 피벗보다 크고 왼쪽이 오른쪽보다 작은 원소를 찾을 때 까지 hi 감소
while(arr[hi] > pivot && lo < hi){
hi--;
}
// hi가 lo보다 크면서, lo의 요소가 pivot보다 큰 원소를 찾을 때 까지 lo 증가
while(arr[lo] <= pivot && lo < hi) {
lo++;
}
// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다
swap(arr,lo,hi);
}
// 마지막으로 맨 처음 pivot으로 설정했는 위치(a[left])의 원소와
// lo가 가리키는 원소를 바꾼다
swap(arr,left,lo);
// 두 요소가 교환되었다면 피벗이였던 요소는 lo에 위치하므로 lo를 반환한다
return lo;
}
private static void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j] ;
a[j] = temp;
}
}
퀵 정렬(중앙 기준)을 사용한 문제 풀이(정답)
package Doit알고리즘코딩테스트.정렬;// @ author ninaaano
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* 왼쪽 기준으로 퀵 정렬을 하니까 시간 초과가 났다. 이게 머선129..
*/
public class P11004_K번째수 {
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());
}
pivot_sort(arr,0,arr.length-1);
System.out.println(arr[k-1]);
}
private static void pivot_sort(int[] arr, int lo, int hi) {
// 정렬할 원소가 1개 이하기 때문에 정렬하지 않고 함수 종료한다
if(lo>=hi) return;
int pivot = partition(arr,lo,hi);
// 재귀(리커시브)
pivot_sort(arr,lo,pivot);
pivot_sort(arr,pivot+1,hi);
}
private static int partition(int[] arr, int left, int right) {
// lo와 hi는 각각 배열의 끝에서 1 벗어난 위치에서 시작한다
int lo = left-1;
int hi = right+1;
int pivot = arr[(left+right)/2]; // 부분 리스트의 중앙 요소
while(true){
/**
* 1 증가 시키고 난 뒤의 lo 위치의 요소가 pivot보다 큰 요소를 찾을때 까지반복
*/
do{
lo++;
}while(arr[lo] < pivot) ;
/**
* 1 감소 시키고 난 뒤의 hi 위치가 lo보다 크거나 같은 위치면서
* hi 위치의 요소가 pivot보다 작은 요소를 찾을 때 까지 반복
*/
do{
hi--;
}while(arr[hi] > pivot && lo <= hi);
/**
* 만약 hi가 lo보다 크지 않다면 (엇갈린다면) swap 하지않고 hi리턴
*/
if(lo>=hi){
return hi;
}
// 교환될 두 요소를 찾았으면 두 요소를 바꾼다
swap(arr,lo,hi);
}
}
private static void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j] ;
a[j] = temp;
}
}
어쩔 때 무슨 기준을 잡아야 하는지를 공부해봐야 할 것 같다..
