[99클럽 4기 코테 스터디 TIL 26일차] K번째 수(feat. 오름차순 정렬)

1) 문제

 

https://www.acmicpc.net/problem/11004

 

 

수 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

 

 

 

 

 

 

 

2) 내가 구현한 코드

• 단순 오름차순 정렬을 구현하는 문제이다.
• 정렬 후 K번째만 출력하면 된다.
• 유의할 점은 index를 이용 시 0부터 카운트 되기 때문에 -1을 해줘야 한다.

① Collections.sort() 이용 : 가장 느림

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //숫자의 갯수
        int K = Integer.parseInt(st.nextToken()); //K번째 수 출력

        ArrayList<Integer> list = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            list.add(Integer.parseInt(st.nextToken()));
        }
        //오름차순 정렬
        Collections.sort(list);
        bw.write(list.get(K-1)+"");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

② Arrays.sort() 이용 : 가장 빠름

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //숫자의 갯수
        int K = Integer.parseInt(st.nextToken()); //K번째 수 출력
        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);

        bw.write(arr[K-1]+"");

        bw.flush();
        br.close();
        bw.close();
    }
}

③ PriorityQueue 우선순위 큐 이용 : 중간속도

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //숫자의 갯수
        int K = Integer.parseInt(st.nextToken()); //K번째 수 출력
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            pq.add(Integer.parseInt(st.nextToken()));
        }

        for(int i=0; i<K-1; i++){
            pq.poll();
        }
        bw.write(pq.poll()+"");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

 

3) 추가 문제

미들러- 돌 게임

https://www.acmicpc.net/problem/9655

챌린저 - 주사위 고르기

https://school.programmers.co.kr/learn/courses/30/lessons/258709

프로그래머스