[JAVA][BOJ][S5] 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번째 있는 수를 출력한다.

풀이

정답 비율이 40퍼센트가 안 될 때부터 불안하긴 했지만 역시나 시간 초과가 떴다

배열을 받은 뒤 정렬을 하는 아주 간단한 문제지만 배열을 사용할 경우 시간 초과가 나서 리스트를 사용하는 것으로 코드를 변경했다 정렬을 사용할 때는 Arrays.sort를, 리스트를 사용할 때는 Collections.sort를 이용했다

코드

package 문제풀이;

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

public class S5_11004_K번째수 {

	public static void main(String[] args) throws Exception {
		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[] A = new int[N]; // 풀이 3
//		List<Integer> A = new LinkedList<>(); // 풀이 2
		List<Integer> A = new ArrayList<>(); // 풀이 1
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			A.add(Integer.parseInt(st.nextToken()));
		}
		
		Collections.sort(A);
		
		System.out.println(A.get(K-1));

	}

}

결과

위에서부터 풀이 1, 2, 3이다

 

#자바 #java #boj #백준 #알고리즘