[99클럽 26일차] [백준] 11004 K번째 수

[백준] 11004 K번째 수

문제 설명

입력으로 주어지는 N개의 정수 배열에서 K번째 작은 수를 출력하는 문제.

입력 조건

• 첫 줄에 정수 N과 K가 주어짐
• 두 번째 줄에 N개의 정수가 공백으로 구분되어 입력

출력 조건:

• N개의 수 중 K번째로 작은 수를 출력

문제 접근

N개의 숫자를 배열또는 리스트에 담아 정렬하고 index 접근하여 K번째로 작은 수를 출력해본다.

PriorityQueue를 하도 많이 썼더니 정렬할 필요도 없이 자동 정렬되니 K번까지 poll해버릴까? 하다가 나오는 수의 범위가 (-10^9 ≤ Ai ≤ 10^9)을 확인하고 접기로 했다. 10^9번째 수 뽑으세요. 하면 효율성 0점이다....

코드 구현

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stk = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(stk.nextToken());
        int K = Integer.parseInt(stk.nextToken());

        List<Integer> list = new ArrayList<>();
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(stk.nextToken()));
        }

        Collections.sort(list);
        System.out.println(list.get(K - 1));
        br.close();
    }
}

코드 분석

정렬을 해야해서 Collections.sort()쓰려고 거의 자동반사격으로 ArrayList에 요소값들을 담았다. 코드 다 작성하고 제출하는데 요소의 개수도 N으로 주어지는데 왜 배열에 안담았지? 하는 생각이 들었다...

채점하는데 너무 느려서 시간초과 뜰까봐 조마조마하면서 이런 생각을 했다.. 아 배열로 풀면 더 빨랐을 것 같은데...

훨 빠르네 젠장

Collections.sort() vs Arrays.sort()

객체형 배열 (List<Integer>)

• Collections.sort() 사용 => 내부적으로 Timsort를 적용하며 안정 정렬을 보장한다.
• 시간 복잡도 : O(NlogN)

기본형 배열 (int[]):

• Arrays.sort() 사용 => 기본 자료형 배열에서는 Dual-Pivot QuickSort를 사용해서 더 빠르고 메모리도 효율적으로 관리한다.
• 시간 복잡도는 O(NlogN) 로 동일 하지만 메모리 사용은 더 적음.

데이터 구조	정렬 알고리즘	평균 시간 복잡도	메모리 사용	속도 비교
int[]	Dual-Pivot QuickSort	(O(n \log n))	(O(\log n))	더 빠름 (원시 배열)
List<Integer>	Timsort	(O(n \log n))	(O(n))	느림 (박싱/언박싱 비용 추가)