[백준 11004] K번째 수 (C#, C++) - soo:bak
작성일 :
문제 링크
설명
주어진 수열을 오름차순 정렬했을 때, 앞에서부터 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;
}