Beakjoon 7469 K번째 수

30 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/7469

나의 풀이

이 문제를 보고 가장 쉽게 접근하면 새로운 배열을 만들어 i부터 j범위 까지 반복해서 정렬하는 방법이 있다. 하지만 이 방법을 사용할 경우 시간 초과가 발생하기 때문에 다른 방식으로 접근을 해야한다.
풀이 방식은 아래와 같다.

1. 각 숫자의 초기 index를 숫자와 묶는다.
2. 배열을 오름차순으로 정렬한다.
3. 배열을 순차적으로 탐색하며 초기 index 값이 i이상 j이하인 경우만 count를 증가시켜 count가 k일 때 까지 반복한다.

문제에서 요구하는 a[i..j]를 정렬했을 때 k번째 수는 결국 i이상 j이하인 초기 index에서 k번째로 큰 값을 찾는 것이기 때문에 위와 같은 풀이를 적용하면 문제를 해결할 수 있다.

풀이 코드 : 11004 K번째 수

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

using namespace std;

struct data_{
    long long num;
    int idx;
};

bool compare(data_ a, data_ b){
    return a.num < b.num;
}

int N, M;
vector<data_> arr;
void Q(int i, int j, int k){
    int count = 0;
    for(int l=0;l<N;l++){
        if(i<=arr[l].idx && arr[l].idx<=j){
            count++;
            if(count == k){
                cout<<arr[l].num<<"\n";
                break;
            }
        }
    }
}

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

    int i, j, k;
    vector<int> I,J,K;
    data_ a;
    cin>>N>>M;
    for(int n=0;n<N;n++){
        cin>>a.num;
        a.idx = n + 1;
        arr.push_back(a);
    }

    for(int m=0;m<M;m++){
        cin>>i>>j>>k;
        I.push_back(i);
        J.push_back(j);
        K.push_back(k);
    }
    sort(arr.begin(), arr.end(), compare);

    for(int t=0;t<I.size();t++){
        i = I[t];
        j = J[t];
        k = K[t];
        Q(i, j, k);
    }
}

채점결과