[7469번] k번째 숫자

문제 출처 :

https://www.acmicpc.net/problem/7463

알고리즘 분석 :

문제 해결에 필요한 사항

1. 배열을 struct화 시켜 값 / 인덱스로 구분하는 응용법

2. 정렬

이 문제는 보통 k -th number 알고리즘을 이용하여 푸는 방식이 대부분이다.

즉, 세그먼트 트리, 펜윅 트리 등등을 이용하여 문제를 접근하는것이 보편적이라고 알고있다.

하지만 이번 게시물에서는 다른 방식을 소개해주고자 한다.

필자도 처음에는 세그먼트 트리에 대한 이해도가 낮아서 k -th number 알고리즘 중 하나인 Quick Search를 이용하였지만, 배열을 다시 정렬 해주는 방식에서 시간초과를 당하고 다른 방식을 고안했다.

우선 struct를 생성하여 int num, int idx를 구성해준다. num은 값이고 idx는 num이 몇번째에 존재하는지 나타낸다.

이 struct를 sort를 통해 arr에 대해 정렬한다. (위의 사진은 정렬전이고 아래 사진은 정렬 후이다.)

그다음 input의 2 5 3이라는 수는 idx 2~5번째중 3번째로 큰 값을 찾으라는 것이다.

결국 2 3 4 5 idx중 3번째로 큰 것을 찾으면 되니 1 3 5 7 2 4 6 순서로 된 idx에서

3이 처음으로 나오니 cnt++ 그다음 5 cnt++ 그다음 2가 나오는데 이때 cnt++을 하면 cnt가 3이 되니 결국 세번째로 크다는 의미이다.

결국 5라는 값이 3번째로 큰 값이라는 의미이다.

소스 코드 : 

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
struct _arr
{
    int num;
    int idx;
};
 
bool comp(_arr const& a, _arr const& b) {
    return a.num < b.num;
}
 
 
_arr arr[5000001];
 
int main()
{
    int n, k, i, j;
    int cnt = 0;
    int start, end, target;
 
    scanf("%d %d", &n, &k);
 
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i].num);
        arr[i].idx = i+1;
    }
 
    std::sort(arr, arr+n, comp);
 
    for (i = 0; i < k; i++)
    {
        scanf("%d %d %d", &start, &end, &target);
        
        for (j = 0; j < n; j++)
        {
            if (start <= arr[j].idx && arr[j].idx <= end)
                cnt++;
 
            if(cnt == target)
            {
                printf("%d\n", arr[j].num);
                break;
            }
 
        }
        cnt = 0;
 
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

아래 코드는 시간 초과를 받은 코드이다.

배열을 다시 원상복귀 시키는 과정에서 시간 초과를 받았고, 이 과정을 조금 더 응용해서 풀어낸 것이 위의 코드이다.

#include <stdio.h>
 
int arr[5000001];
int tmp[5000001];
 
void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
 
        while (pivot <= arr[high] && high >= (left + 1)) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
 
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
int QuickSearch(int arr[], int left, int right, int k)
{
    int pivot = Partition(arr, left, right); // 둘로 나누어서
    if (pivot == k)
        return arr[pivot];
 
    else if (pivot > k)
        QuickSearch(arr, left, pivot - 1, k); // 왼쪽 영역을 정렬한다.
 
    else
        QuickSearch(arr, pivot + 1, right, k); // 오른쪽 영역을 정렬한다.
}
 
 
 
int main()
{
    int n, k, i;
    int cnt = 0;
    int start, end, target;
 
    scanf("%d %d", &n, &k);
 
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
        tmp[i] = arr[i];
    }
 
    for (i = 0; i < k; i++)
    {
        scanf("%d %d %d", &start, &end, &target);
        printf("%d\n", QuickSearch(arr +(start - 1), 0, end - start, target-1));
 
        for (int j = start - 1; j <= end - 1; j++)
            arr[j] = tmp[j];
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>