백준 7469번 K번째 숫자

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

정해는 Persistent Segment Tree 혹은 Merge Sort Tree를 통해 푸는 문제였지만 아직 세그먼트 트리에 대한 개념을 완벽히 이해한 상태가 아니였기 때문에 다른 방식으로 풀었습니다.

백준님의 세그먼트 트리 강의와 코드를 참고하여 세그먼트 트리 개념을 익힌 후 다시 풀어볼 생각입니다!

알고리즘은 아래와 같습니다.

1. pair<int, int> 배열을 선언하여 first에는 값, second에는 인덱스를 저장합니다.

2. 값을 기준으로 오름차순 정렬을 합니다.

3. 배열을 처음부터 순회하는데 인덱스 즉, second가 start 이상이고 end 이하인 숫자를 발견하면 cnt를 증가시킵니다.

4. cnt가 K가 되면 주어진 범위 내 K 번째 숫자를 찾게 된 것이므로 해당 숫자 즉, first를 출력해주면 됩니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 100000;

int N, M;

pair<int, int> arr[MAX + 1]; //value, idx

 

int Kth(int start, int end, int k)

{

        int cnt = 0;

        for (int i = 0; i < N; i++)

        {

                 //second가 인덱스이므로

                 if (start <= arr[i].second && arr[i].second <= end)

                         cnt++;

 

                 //k 번째 숫자 반환

                 if (cnt == k)

                         return arr[i].first;

        }

        return -1;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

        {

                 cin >> arr[i].first;

                 arr[i].second = i + 1;

        }

 

        //value 기준으로 오름차순 정렬

        sort(arr, arr + N);

 

        for (int i = 0; i < M; i++)

        {

                 int start, end, k;

                 cin >> start >> end >> k;

 

                 cout << Kth(start, end, k) << "\n";

        }

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~