엘리스 코드 챌린지 예선 [Day 2] 문제풀이

문제

목표량

시간 제한: 1초

정리 정돈을 좋아하는 k씨의 본명은 아무도 모릅니다.

사람들은 k씨의 특이한 행동 2가지 때문에 그를 '정리 정돈을 좋아하는 k씨'라고 부릅니다. 그 두 가지 행동은 그가 숫자를 정리하는 일을 하면 아무 규칙없이 나열되어 있는 숫자중 범위를 정한 후 무조건 오름차순으로 정리한다는 것, 그리고 오름차순으로 정리된 숫자 중 k번째 숫자를 선택한다는 것입니다

예를 들어 a={1, 7, 6, 8, 1, 6, 4, 5}라는 수열이 있습니다.

정리정돈을 좋아하는 k씨는 범위를 2에서 5로 정하고, k를 2라고 정했습니다.

그러면 ka ={7, 6, 8, 1}이 되고, 이것을 오름차순으로 정리를 하면

ka ={1, 6, 7, 8}이 됩니다. 그리고 k씨는 2번째인 6을 선택합니다.

배열 a가 주어지고, k씨가 일을 한 횟수가 주어졌을 때, k씨가 고른 숫자를 출력하는 프로그램을 작성하세요.

지시사항

입력

첫째 줄에 배열의 크기인 정수 n과 k씨가 일한 횟수인 정수 m을 입력합니다.

1 ≤ n ≤ 10000

1 ≤ m ≤ 500

둘째 줄에는 배열에 포함된 정수를 순서대로 입력합니다. 각 정수는 절댓값이 200을 넘지 않는 정수입니다.
다음 줄 부터 m개 줄에 걸쳐 k씨가 고른 범위인 정수 i, j와 정수 k를 입력합니다.

1 ≤ i ≤ j ≤ n

1 ≤ k ≤ j − i + 1

출력

k씨가 일할 때마다 k씨가 선택한 숫자를 한 줄에 하나씩 출력합니다.

입력 예시

8 3
1 7 6 8 1 6 4 5
1 5 3
2 6 2
4 8 3

출력 예시

6
6
5

풀이

접근

접근 방법에 대해 생각해 보자.

범위나 주어지는 수들의 크기가 않아서 주어진 조건들을 그대로 코드로 구현해봤다.

풀이

벡터 두개를 선언한 후 두번째 벡터에 범위에 해당하는 값들을 넣어준다.
정렬 한다.
k번째 값을 출력한다.
1~3번 과정을 m번 반복한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, i, j, k, t, q;
    vector<int> a, b;

    cin >> n >> m;
    a.resize(n + 1);
    for (t = 1; t < n + 1; t++)
        cin >> a[t];

    for (t = 0; t < m; t++)
    {
        cin >> i >> j >> k;
        b.resize(0);

	// 범위에 해당하는 값들을 벡터 b에 넣어준다
        for (q = i; q <= j; q++)
            b.push_back(a[q]);

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

        cout << b[k - 1] << '\n';
    }

    return 0;
}

↑ 더보기 클릭으로 펼치기

모범답안

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

vector<int> seq;
int main() {
  int n, m, i, j, k, tmp;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> tmp;
    seq.push_back(tmp);
  }
  for (int cnt = 0; cnt < m; cnt++) {
    cin >> i >> j >> k;
    vector<int> part = vector<int>(seq.begin() + i - 1, seq.begin() + j);
    sort(part.begin(), part.end());
    cout << part[k - 1] << endl;
  }
}