💎 문제
버블 정렬이란, 두 인접한 원소를 검사하여 자리를 바꾸는 방식으로 길이가 N인 수열을 정렬하는 알고리즘이다. 버블 정렬은 아래와 같은 단계를 총 N번 진행하면 된다.
- 첫 번째 값과 두 번째 값을 비교하여 첫 번째 값이 더 크면 자리를 바꾼다.
- 두 번째 값과 세 번째 값을 비교하여 두 번째 값이 더 크면 자리를 바꾼다.
- …
- N - 1번째 값과 N번째 값을 비교하여 N - 1번째 값이 더 크면 자리를 바꾼다.
세찬이는 버블 정렬의 결과는 당연히 알기에 버블 정렬의 중간 과정을 알아보려고 한다. 하지만 N이 매우 크므로 위와 같은 단계를 K번 하면 시간이 오래 걸린다. 세찬이를 도와 버블 정렬의 중간 과정을 구하는 프로그램을 작성하여라.
💎 입력
첫 번째 줄에는 N과 K가 주어진다.
두 번째 줄에는 처음 수열의 상태가 주어진다. 즉, 처음 수열을 이루는 N개의 정수가 공백을 사이로 두고 차례대로 주어진다.
- 1 ≤ N ≤ 100,000
- 1 ≤ K ≤ N
- 수열의 각 항은 1 이상 1,000,000,000 이하의 정수이다.
ex)
4 1
62 23 32 15
💎 출력
위 단계를 K번 한 후 수열의 상태를 출력한다.
ex)
23 32 15 62
💎 풀이 방법
첫 백준 플래티넘 문제였다..!!! 친구가 풀었던 문제이고 플래티넘 치고는 아이디어 있으면 금방 푼다고 했는데 우선 순위 큐를 사용하여 푼다는 문제에서 굉장히 큰 힌트였던 것 같다. 문제는 버블정렬 시간 복잡도가 n^2의 형태로 굉장히 효율이 좋지 못한 정렬알고리즘의 과정을 출력으로 보여주는 것이 문제였다!! 수열의 크기가 100,000으로 굉장히 크기 때문에 무조건 시간초과가 발생하는 문제여서 하나하나 비교하는 풀이가 아닌 다른 방식으로 버블정렬의 방식으로 보여주여야 하는 문제였다!!
이 때 이러한 우선 순위 큐를 이용하여 문제를 풀어주면 되었는데, 우선순위 큐는 큐와 같은 방식에서 큐에 값을 삽입하면 크기에 따라서 큐 안에 순서가 바뀌는 방식이다. 따라서 이를 이용하여 버블정렬의 K번째 단계의 수열 상태를 구하기 위해서 K개 만큼의 수열의 값을 먼저 우선 순위 큐에 넣어주고 시작하는 것이 중요하다!!
for(int i = 0;i < K;i++)
q.push(v[i]);
for(int i = 0;i < N - K;i++){
q.push(v[i + K]);
v[i] = q.top();
q.pop();
}이유는 예를들어 1번 째 단계의 버블 정렬을 한다고 생각했을 때 가장 큰 값은 맨 뒤로 갈 것을 생각하면 그렇다. 가장 큰 값은 정렬시 뒤에 갈 것이고 작은 값들을 버블정렬에서 한 칸 씩 앞으로 올 것이다. 왜냐하면 작은 값은 비교시 앞으로 이동하고 다음 차례 검사에서 다시 활용하지 않기 때문에 한 단계를 검사할 때 작은 값은 최대 한 칸만 앞으로 올 수 있다. 따라서 K단계의 버블정렬 결과를 보고 싶다면 먼저 수열의 K개 만큼의 앞에서 부터 값을 우선 순위 큐에 넣어준 뒤 그 우선순위 큐에 나머지 것들을 차례대로 하나씩 넣어보고 그 순간의 작은 값인 top()으로 수열에 다시 저장해서 삭제해줄 것이다.
for(int i = 0;i < N - K;i++)
cout << v[i] << " ";
while(!q.empty()){
cout << q.top() << " ";
q.pop();
}따라서 이를 통해 K번 째 단계에서의 수열은 N-K개 만큼 먼저 출력해주고 나머지 우선 순위 큐에 담긴 것들을 차례대로 출력해준다.
우선 순위 큐에 K개의 크기만큼 값들이 유지되어야한다. 앞에서 말했듯이 K번째의 단계에서는 최소한 K개 만큼의 수가 정렬된 자리에 위치해 있어야한다. 이는 가장 큰 값은 맨 뒤로, 작은 값은 한 칸씩 앞으로 이동하기 때문에 K번 째 단계에서는 K개의 만큼에 단계 별로 가장 컸던 값이 맨 뒤로 와야한다.
조금 난해한데,,, 많이 어려웠다 ㅠㅠ
💎 전체 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(int argc, const char * argv[]) {
int N, K;
priority_queue<int, vector<int>, greater<int>> q;
cin >> N >> K;
vector<int> v(N + 1);
for(int i = 0;i < N;i++)
cin >> v[i];
for(int i = 0;i < K;i++)
q.push(v[i]);
for(int i = 0;i < N - K;i++){
q.push(v[i + K]);
v[i] = q.top();
q.pop();
}
for(int i = 0;i < N - K;i++)
cout << v[i] << " ";
while(!q.empty()){
cout << q.top() << " ";
q.pop();
}
cout << "\n";
return 0;
}💎 고민
첫 플래티넘 문제였는데 아이디어를 생각하기가 어려웠던 문제여서 우선 순위 큐를 이용하여 푸는 문제라는 것을 알고 푸는 것과 모르고 푸는 것에 난이도가 굉장히 달라지는 문제인 것 같다. 요새 계속 우선 순위 큐를 이용하여 푸는 문제들을 접하고 있는데, 코딩 테스트에서도 이를 활용할 수 있으면 좀 더 접근하기 어려웠던 문제를 쉽게 풀어낼 수 있을 것 같다!!
화이팅!!
