작성일 :

문제 링크

11004번 - K번째 수

설명

주어진 수열을 오름차순 정렬했을 때, 앞에서부터 K번째 수를 찾는 문제입니다.

  • 수열의 길이는 최대 5,000,000까지 주어질 수 있으며,
  • K번째 수란 정렬된 수열에서 인덱스 K-1 위치에 있는 수를 의미합니다.

정렬 이후 해당 인덱스의 값을 출력하면 됩니다.


접근법

주어진 수열을 오름차순으로 정렬한 뒤, 앞에서부터 K번째에 위치한 수를 그대로 출력하면 됩니다.

정렬에는 일반적인 \(O(N \log N)\) 시간 복잡도의 정렬 알고리듬을 사용합니다.

수열의 길이는 최대 5,000,000까지 주어지지만, 표준 정렬 알고리듬으로도 제한 시간 내에 충분히 처리할 수 있습니다.


이와 같이 수열을 정렬한 뒤 K - 1번째 인덱스의 값을 그대로 출력하는 방식으로 가장 간단하게 문제를 해결할 수 있습니다.



Code

C#

1
2
3
4
5
6
7
8
9
10
11
12
using System;
using System.Linq;

class Program {
  static void Main() {
    var inputs = Console.ReadLine().Split().Select(int.Parse).ToArray();
    int n = inputs[0], k = inputs[1];
    var arr = Console.ReadLine().Split().Select(int.Parse).ToArray();
    Array.Sort(arr);
    Console.WriteLine(arr[k - 1]);
  }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int len, k; cin >> len >> k;

  vi seq(len);
  for (int i = 0; i < len; i++)
    cin >> seq[i];

  sort(seq.begin(), seq.end());

  cout << seq[k - 1] << "\n";

  return 0;
}