[2075번] N번째 큰 수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Sort

2. Quick Search

이 문제는 Quick Sort, Merge Sort 등등 다양한 nlogn 소팅으로 풀 수 있다.

하지만 http://programbasic.tistory.com/403 이 문제와도 동일하다.

위의 링크 문제가 10개의 값 중 2번째수를 찾는것이라면 이번 문제는 10개의 값중 (10-2)번째 수를 찾는 것과 같다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

#include <stdio.h>   int arr[2250001];   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;       scanf("%d",&k);            for (i = 0; i < k*k; i++)         scanf("%d", &arr[i]);       printf("%d", QuickSearch(arr, 0, k*k - 1, (k*k)-k));          return 0; }     //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus