BOJ 11920. 버블 정렬

🙇‍♀️[Platinum II] 버블 정렬 - 11920

문제 링크

성능 요약

메모리: 3308 KB, 시간: 36 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐

제출 일자

2024년 2월 17일 14:15:04

문제 설명

버블 정렬이란, 두 인접한 원소를 검사하여 자리를 바꾸는 방식으로 길이가 N인 수열을 정렬하는 알고리즘이다. 버블 정렬은 아래와 같은 단계를 총 N번 진행하면 된다.

• 첫 번째 값과 두 번째 값을 비교하여 첫 번째 값이 더 크면 자리를 바꾼다.
• 두 번째 값과 세 번째 값을 비교하여 두 번째 값이 더 크면 자리를 바꾼다.
• …
• N - 1번째 값과 N번째 값을 비교하여 N - 1번째 값이 더 크면 자리를 바꾼다.

세찬이는 버블 정렬의 결과는 당연히 알기에 버블 정렬의 중간 과정을 알아보려고 한다. 하지만 N이 매우 크므로 위와 같은 단계를 K번 하면 시간이 오래 걸린다. 세찬이를 도와 버블 정렬의 중간 과정을 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 N과 K가 주어진다.

두 번째 줄에는 처음 수열의 상태가 주어진다. 즉, 처음 수열을 이루는 N개의 정수가 공백을 사이로 두고 차례대로 주어진다.

• 1 ≤ N ≤ 100,000
• 1 ≤ K ≤ N
• 수열의 각 항은 1 이상 1,000,000,000 이하의 정수이다.

출력

위 단계를 K번 한 후 수열의 상태를 출력한다.

🚀풀이

버블 정렬의 k 번째 상황을 출력해야하는 문제이다.

실제로 버블 정렬을 만들어서 k번째 상황에 출력을 하면 시간 초과가 무조건 난다.

그럼 다른 방식으로 풀어야하는데 우선 순위 큐를 이용해서 푸는 방식이다.

먼저 입력값을 받는다.

int n, k;
vector<int> v;
priority_queue<int, vector<int>, greater<int>> q;

cin >> n >> k;
v = vector<int>(n);

for (int i = 0; i < n; ++i)
{
    cin >> v[i];
}

그 뒤 k까지만 우선 순위 큐에 넣는다.

for (int i = 0; i < k; ++i)
{
	q.push(v[i]);
}

아래가 중요한데 q에 v[i + k]를 넣고 v[i]를 q.top으로 갱신한다.
그 뒤 q.pop을 해준다.
v[i]가 바뀐다는게 중요한데 예제를 그대로 가져와서 이해를 하자.

4 1
62 23 32 15

v : 62 23 32 15
q : 23 62

v : 23 23 32 15
q : 32 62

v : 23 32 32 15
q : 15 62

v : 23 32 15 15
q : 62

이렇게 변한다.

for (int i = 0; i < n - k; ++i)
{
	q.push(v[i + k]);
	v[i] = q.top();
	q.pop();
}

n - k까지 v[i]를 출력하고 남아있는 큐 값들을 다 출력하면 된다.

for (int i = 0; i < n - k; ++i)
	cout << v[i] << " ";

while (q.empty() == false)
{
	cout << q.top() << " ";
	q.pop();
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

int n, k;
vector<int> v;
priority_queue<int, vector<int>, greater<int>> q;
void solve()
{
	cin >> n >> k;
	v = vector<int>(n);

	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() == false)
	{
		cout << q.top() << " ";
		q.pop();
	}
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}