[java] 문제 019 (백준 11004)

문제

K번째 수

 

교재 풀이

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

public class P11004_K번째수 {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(in.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(in.readLine());
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    quickSort(A, 0, N - 1,  K - 1);
    System.out.println(A[K - 1]);
  }
  public static void quickSort(int[] A, int S, int E, int K) {
      if(S<E){
      int pivot = partition(A, S, E);
      if (pivot == K) { //K번째 수가 pivot이면 더이상 구할 필요 없음
        return;
      }
      else if(K < pivot) {  //K가 pivot보다 작으면 왼쪽만 정렬
        quickSort(A, S, pivot - 1, K);
      }
      else if(K > pivot){  //K가 pivot보다 크면 왼쪽만 정렬
        quickSort(A, pivot+1, E, K);
      }
          }
  }

  private static int partition(int[] A, int S, int E){
    if(S+1==E) {
      if(A[S]>A[E])swap(A,S,E);
      return E;
    }
    int M = (S + E) / 2;
    swap(A, S, M); // 중앙값을 1번째 요소로 이동하기
    int pivot = A[S];
    int i = S+1, j = E;
    
    while (i <= j) {
        while (pivot < A[j] && j > 0 ){   //피벗보다 작은 수가 나올때까지 j--
            j--;    
        }
        while (pivot > A[i]  && i <A.length-1){  //피벗보다 큰 수가 나올 떄까지 i++
               i ++;  
        }
        if (i <= j) {
            swap (A, i++, j--);  // 찾은 i와 j를 교환하기
        }
    }
    // i == j 피벗의 값을 양쪽으로 분리한 가운데에 오도록 설정하기
    A[S] = A[j];
    A[j] = pivot;
    return j;
}
  
  public static void swap(int[] A, int i, int j) {
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
  }
}

 

내 풀이) 24.6.10에 풀고 틀림

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws IOException {
// 		수 N개 A1, A2, ..., AN이 주어진다. 
// 		A를 오름차순 정렬했을 때, 
// 		앞에서부터 K번째 있는 수를 구하는 프로그램
		
// 		첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
// 		둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)
// 		A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.
	    
// 	    입력
// 	        5 2
//             4 1 2 3 5
//                 5가 n이고 
//                 2가 k, 2번째 있는 수 구해라는 뜻 
//         출력 
//             2 
//                 오름차순 정렬한 배열이 12345니까 두 번째는 2가 나오네 
//                 즉 배열 인덱스가 1부터 시작하네 
//         접근법
//             n이 오백만이라, nlogn 하면 10의 6제곱 곱하기 log 10의 6제곱(10의 6제곱은
//             2의 10제곱이 10의 3제곱이니까 2의 20제곱이고 그럼 log2의 20제곱은 20이 되
//             어서)20곱하기 5곱하기 10의 6제곱은 10의 2제곱 곱하기 10의 6제곱은 10의 8
//             제곱이고 그럼 1억 쯤 되니까 제한 시간 내에 골인 
//             그냥 array.sort 쓰면 될 듯, 너무 간단한데 
//         슈도 코드
//             n 입력받기 
//             k 입력받기 
//             수자 n개 정수 배열에 입력받기 
//                 입력은 bufferedReader 쓰면 될 듯 
//                 배열 크기는 n+1 사용하고 
//                 for문 이용해서 인덱스 1부터 저장하기 
            
//             arrays.sort 사용하기 
            
//             k번째 원소 출력하기 
            
        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+1];
        for(int i=1;i<=n;i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(arr);
        
        System.out.println(arr[k]);
	}
}

 

설명

일단 6.10엔 정렬 구현 없이 Arrays.sort를 써서 했는데도 틀림

왜? 배열 크기를 n+1하고, 1부터 채워넣으면

sort하면 0번째 인덱스의 0이 섞여서 정렬됨

따라서 입력값으로 받는 것과 섞여서 잘못된 답이 나옴

 

다음엔 한 번 정렬 원리 구현해서 해 보는 것도 좋겠다고 생각함