comkiwer- Tutorial: STL Sort 3 > 문제은행 : 정보올림피아드&알고리즘



3520 : Tutorial: STL Sort 3

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
139 회   
시도횟수
364 회   

문제

STL(Standard Template Library-표준 템플릿 라이브러리)는 알고리즘(Algorithm), 컨테이너(container), 

함수객체(functions), 반복자(iterator)로 구성된 C++을 위한 라이브러리(Library) 이다. 

STL에는 많은 유용한 내용들이 있지만 여기서는 <algorithm> 헤더에 포함된 sort함수를 집중하여 다루어 본다.

 

[ std::sort ]

0. 함수 원형은 두 가지 포맷이 있다.

   (1) void sort (RandomAccessIterator first, RandomAccessIterator last);
       sort(구간의 시작 포인터, 구간의 끝 포인터);                    // last는 마지막 유효포인터 + 1 임에 유의한다.

   (2) void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
       ​sort(구간의 시작 포인터, 구간의 끝 포인터, 정렬기준함수[객체]);​ // 따라서 구간범위는[first, last) 이다.

1. <algorithm> 헤더를 include 하거나 이 헤더를 포함하는 다른 어떤 헤더를 include 하여 사용한다.(g++ 예: <bits/stdc++.h>)

2. O(N logN) 의 실행속도를 보장한다. 

   : stl-sort 를 intro-sort(introspective sort : 자기성찰적인 정렬^^)라고 하는데 그 이유는 다음 3가지 정렬을 포함하고 있기 때문이다.

   (1) GCC의 경우 원소의 수가 16이하인 경우 삽입정렬을 이용한다.(<bits/stl_algo.h> 에서 _S_threshold = 16)
       (VC++ 은 32 이하 : <algorithm> 에서 _ISORT_MAX로 확인가능하다.)
   (2) 그 외의 경우 퀵정렬을 이용하여 정렬하는데 

   (3) 재귀의 깊이가 logN을 넘어가는 경우 힙정렬(logN을 보증하는 정렬)을 이용한다.

3. 사용법을 잘 익힌다면 정수, 문자, 실수, 문자열, 객체 등의 배열을 원하는 방법으로 정렬시킬 수 있다.

 

[정수 배열을 정렬하기]

std::sort 함수를 이용하여 정수 배열을 정렬하는 여러가지 방법을 살펴보자.

 

  1. #include <cstdio>
  2. #include <algorithm>   // sort 함수를 사용하기 위하여
  3. #include <functional>  // greater 클래스를 사용하기 위하여
  4. using namespace std;
  5.  
  6. bool comp(int a, int b){return a > b;}
  7.  
  8. struct Comparator{
  9.     bool operator()(const int&a, const int&b){
  10.         return a > b;
  11.     }
  12. }compareObject;
  13.  
  14. int main(){
  15.     int A[10] = {7, 2, 3, 8, 1, 10, 4, 6, 5, 9};
  16.  
  17.     // 원하는 영역을 오름차순 정렬하기
  18.     sort(A, A+5);          // (1, 2, 3, 7, 8), 10, 4, 6, 5, 9
  19.     for(int i=0;i<10 ; ++i) printf("%d ", A[i]); puts("");
  20.  
  21.     // 함수를 이용하여 원하는 영역을 내림차순 정렬하기
  22.     sort(A+5, A+10, comp); // 1, 2, 3, 7, 8, (10, 9, 6, 5, 4)
  23.     for(int i=0;i<10 ; ++i) printf("%d ", A[i]); puts("");
  24.  
  25.     sort(A, A+10);         // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  26.     for(int i=0;i<10 ; ++i) printf("%d ", A[i]); puts("");
  27.  
  28. //    // *** 아래 4가지 유형은 시간을 두고 천천히 익혀보자. ***
  29. //    // 클래스 greater 이용
  30. //    sort(A, A+10, greater<int>()); // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
  31. //    for(int i=0;i<10; ++i) printf("%d ", A[i]);
  32. //    puts("");
  33. //
  34. //    // lambda 이용
  35. //    sort(A, A+10, [&](int a, int b){return a<b;}); // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  36. //    for(int i=0;i<10; ++i) printf("%d ", A[i]);
  37. //    puts("");
  38. //
  39. //    // 사용자정의 함수객체클래스생성자 사용
  40. //    sort(A, A+10, Comparator());    // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
  41. //    for(int i=0;i<10; ++i) printf("%d ", A[i]);
  42. //    puts("");
  43. //
  44. //    // 사용자정의 함수객체 사용
  45. //    sort(A, A+10, compareObject);   // 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
  46. //    for(int i=0;i<10; ++i) printf("%d ", A[i]);
  47. //    puts("");
  48.  
  49.     return 0;
  50. }

 

[객체 배열을 정렬하기]

std::sort 함수를 이용하여 객제 배열을 정렬하는 여러가지 방법을 살펴보자.

  1. #include <cstdio>
  2. #include <cstring>     // for strcmp
  3. #include <algorithm>   // for sort
  4. using namespace std;
  5.  
  6. struct Data{
  7.     int grade;
  8.     char name[30];
  9.  
  10. // 1. 클래스내 연산자 오버로딩 하기
  11.     bool operator<(const Data&r) const{
  12.         if(grade != r.grade){           // 학년의 내림차순을 1순위로 정렬
  13.             return grade > r.grade;
  14.         }
  15.         return strcmp(name, r.name) < 0;// 이름의 오름차순을 2순위로
  16.     }
  17.     void output(){
  18.         printf("{%d \"%s\"} ", grade, name);
  19.     }
  20. };
  21.  
  22. //// 2. 클래스밖 전역함수에 의한 연산자 오버로딩 하기
  23. //bool operator<(const Data&a, const Data&b){
  24. //    if(a.grade != b.grade){            // 학년의 내림차순을 1순위로
  25. //        return a.grade > b.grade;
  26. //    }
  27. //    return strcmp(a.name, b.name) < 0; // 이름의 오름차순을 2순위로 정렬
  28. //}
  29.  
  30. bool comp(const Data&a, const Data&b){
  31.     if(a.grade != b.grade){            // 학년의 오름차순을 1순위로
  32.         return a.grade < b.grade;
  33.     }
  34.     return strcmp(a.name, b.name) < 0; // 이름의 오름차순을 2순위로 정렬
  35. }
  36.  
  37. struct Comparator{
  38.     bool operator()(const Data&a, const Data&b){
  39.         if(a.grade != b.grade){            // 학년의 오름차순을 1순위로
  40.             return a.grade < b.grade;
  41.         }
  42.         return strcmp(a.name, b.name) > 0; // 이름의 내림차순을 2순위로 정렬
  43.     }
  44. }compObject;
  45.  
  46. int main(){
  47.     Data arr[] = {{3, "Nana"}, {6, "Titus"}, {3, "Amy"}, {6, "Dewey"}, {5, "Olivia"}};
  48.     /// 1, 2 연산자 오버로딩 사용하기
  49.     sort(arr, arr+5);
  50.     // {6, "Dewey"} {6, "Titus"} {5, "Olivia"} {3, "Amy"} {3, "Nana"}
  51.     for(int i=0;i<5;++i) arr[i].output(); puts("");
  52.  
  53.     // 3. 비교함수 사용하기
  54.     sort(arr, arr+5, comp);
  55.     //{3, "Amy"} {3, "Nana"} {5, "Olivia"} {6, "Dewey"} {6, "Titus"}
  56.     for(int i=0;i<5;++i) arr[i].output(); puts("");
  57.  
  58.  
  59. //    // *** 아래 유형이 이해하기 힘들다면 시간을 두고 천천히 연구해보자. ***
  60. //    // 4. 람다함수 사용하기
  61. //    sort(arr, arr+5, [&](const Data&a, const Data&b){
  62. //         if(a.grade != b.grade) return a.grade > b.grade;// 학년의 내림차순을 1순위로
  63. //         return strcmp(a.name, b.name) > 0;              // 이름의 내림차순을 2순위로 정렬
  64. //         });
  65. //    // {6, "Titus"} {6, "Dewey"} {5, "Olivia"} {3, "Nana"} {3, "Amy"}
  66. //    for(int i=0;i<5;++i) arr[i].output(); puts("");
  67. //
  68. //    // 5. 함수객체 사용하기
  69. //    sort(arr, arr+5, Comparator());
  70. //    sort(arr, arr+5, compObject);
  71. //    //{3, "Nana"} {3, "Amy"} {5, "Olivia"} {6, "Titus"} {6, "Dewey"}
  72. //    for(int i=0;i<5;++i) arr[i].output(); puts("");
  73.  
  74.     return 0;
  75. }




[문제]

N명의 학생정보를 입력받아 정렬 규칙에 맞게 정렬한 후 Q개의 질의에 답하는 프로그램을 작성하시오.

학생정보는 1 ~ 10만 이하의 정수 ID, 10자이하의 영문대문자 이름, 100만 이하의 정수 선호도로 이루어진다.

i번째 학생의 ID는 i이다. ( 1≤ i ≤​ N)

정렬 규칙은 선호도의 내림차순을 1순위로 이름의 오름차순을 2순위로 ID의 오름차순을 3순위로 한다.

ID는 유일하며 이름과 선호도는 같은 값이 있을 수 있다.

질의는 정렬 후 K번째 학생의 ID를 구하는 것이다.

 


입력형식

첫 행에 N과 Q가 공백을 구분하여 주어진다. ( 5 ≤​ N, Q ≤​ 100,000)

다음 N개의 행에 학생의 정보 이름과 선호도 Pi가 주어진다. ( 0 ≤​ Pi ≤​ 100,000) 

ID는 입력순서대로 1 ~ N까지이다. 

마지막 행에 Q개의 질의가 공백을 구분하여 주어진다.


출력형식

Q개의 질의에 대하여 해당하는 학생의 ID를 공백으로 구분하여 출력한다.

입력 예

5 5
Nana 7
Titus 9
Titus 3
Amy 3
Olivia 8
1 2 3 4 5

출력 예

2 5 1 4 3

Hint!

* string, pair, turple, vector 등과 관련한 내용은 다른 문제에서 다룬다.


출처

comkiwer

STL, sort, Tutorial

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP