[99클럽 코테 스터디 26일차 TIL] #정렬1

26일 차입니다. 어제 블로그를 써놓고 링크를 안 올렸어요.. 아,, 짜증이 확,,

그리고 친구들이랑 놀다가 오늘 풀어야 할 문제가 있다는 것을 깜빡할 뻔했습니다. 새벽 4시에 부랴부랴 쓰네요 ㅎ..

미리미리 해야하는 건데 사람이 게을러가지고 -- 아무튼 이상한 소리 그만하고 빨리 풀고 자러 가보도록 하겠습니다.

 

문제 설명 

---

 

굉장히 간단한 문제였습니다. 숫자의 개수 n과 수 k가 주어지고 n개의 정수가 주어집니다. n개의 정수를 오름차순으로 정렬해서 k번째 수를 출력하면 되는 쉬운 문제였습니다.

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

 

 

생각 흐름

---

시간도 늦었는데 너무 쉬운 문제다 싶어서 기분 좋게 빠르게 벡터를 이용해서 풀었었습니다.

 

정수를 담을 벡터를 선언하고 이를 일일이 넣어준 다음 <algorithm> 헤더파일 내에 있는 sort() 함수를 사용해 정렬을 시킨 후 벡터의 요소를 출력해 주었습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    int n, k;
    cin >> n >> k;

    vector <int> v; // 수를 저장할 배열
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    sort(v.begin(), v.end());

    cout << v[k-1] << "\n";

    return 0;
}

 

와 너무 쉽다~! 하고 끝내려는데 시간초과가 뜬 겁니다.

또 빨리 풀고자 하는 마음에 시간제한을 신경을 쓰지 못했다는 것이었죠,

 

N의 범위가 1~5000000까지였고 들어오는 정수 A는 -10^9~10^9 까지였으니 단순한 반복문과 sort()로는 너무 데이터 양이 많아 시간초과 나는 것이 당연했습니다.

 

그래서 예전에도 이런 비슷한 상황을 겪어봤어서 k번째 작은 수를 출력을 한다면 정수를 담는 자료구조 내에 k개의 요소만 남기자!라는 생각을 하였습니다.

 

우선, 오름차순 정렬을 할 거니까 당연하게도 우선순위 큐를 오름차순으로 선언해 주었습니다.

priority_queue <int> pq;

 

곰곰이 생각을 해보니 k번째 작은 수를 출력을 할 것이고 k개의 원소만을 자료구조에 남기려면 큰 수들을 제거를 해줘야 하므로 pq를 뒤집어서 내림차순으로 정의를 내려야겠구나 싶어서  great <int>를 이용해 내림차순으로 정렬되게 바꾸어주고

 

반복문 내에 pq.size()가 k보다 크다면 pq.top()이 제거가 되어 k개의 요소만 자료구조에 남게 설정해 주었습니다.

 

그러고 나서 반복문이 끝나고 나선 k번째 작은 수가 pq.top()에 저장돼 있을 테니 pq.top()을 출력해 주며 마무리하였습니다

 

#include <iostream>
#include <queue>
using namespace std;

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

    int n, k;
    cin >> n >> k;

    // 문제는 k번째로 작은 수를 출력하고 싶어함
    priority_queue <int> pq; // 수를 내림차순으로 저장할 우선순위 큐 pq 선언
    // 큰 수들이 top()에 올라오게 됨
    
    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        pq.push(temp);

        if (pq.size() > k) { // k개의 수를 넘으면
            pq.pop(); // 제거 (자동으로 작은 수가 제거됨)
        }
    }
    
    cout << pq.top() << "\n";
    return 0;
}​

 

 

 

공부한 내용 정리

---

이번 문제에서는 새로운 개념을 공부했다기 보단 지금까지 해왔던 꾸준한 학습이 도움이 되는구나를 몸소 느꼈던 문제였던 것 같습니다.

 

힙과 관련된 문제를 풀면서 비슷한 상황과 풀이법을 공부했던 기억이 있는데 꾸준히 공부를 하니 이를 바탕으로 스스로 그 풀이법을 생각해 내어 풀이를 했다는 것이 뿌듯했습니다.