취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1071번 문제인 소트이다.
문제는 아래 링크를 확인하자.

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

현재 남아있는 수 중 가장 작은 수를 최대한 먼저 사용해나가야 사전순으로 가장 빠른 배열이 되게끔 수들을 나열할 수 있을 것이다. 아직 나열하지 않은 가장 작은 수를 mn1, 두번째로 작은(mn1과 다른) 수를 mn2라 하고 바로 이전에 사용한 수를 old라 할 때(초기값은 음의 무한대), old + 1 = mn1을 만족한다면 mn2를, 그렇지 않다면 mn1를 다음 수로 나열해나가자. 단, 아직 나열하지 않은 서로 다른 수가 mn1과 mn2두 종류뿐이고(mn1 < mn2) mn1 + 1 = mn2를 만족한다면 mn2를 먼저 전부 나열하고 남은 mn1을 나열해주자.

위와 같은 작동을 하는 코드를 작성해 문제를 해결하자. 글쓴이는 스택 자료구조를 이용하여 위 내용을 구현했다.

아래는 제출한 소스코드이다.

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

int cnt[1001];
vector<pair<int, int>> stk;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	while (N--) {
		int x; cin >> x;
		cnt[x]++;
	}

	for (int i = 1000; i > -1; i--) {
		if (cnt[i]) stk.emplace_back(make_pair(i, cnt[i]));
	}

	while (stk.size() > 2) {
		auto p1 = stk.back(); stk.pop_back();
		auto p2 = stk.back(); stk.pop_back();
		auto p3 = stk.back(); stk.pop_back();
		for (int k = 0; k < p1.second; k++) cout << p1.first << ' ';
		if (p1.first + 1 == p2.first) {
			cout << p3.first << ' ';
			p3.second--;
		}
		if (p3.second) stk.emplace_back(p3);
		stk.emplace_back(p2);
	}

	if (stk.size() == 2) {
		auto p1 = stk.back(); stk.pop_back();
		auto p2 = stk.back(); stk.pop_back();
		if (p1.first + 1 == p2.first) {
			for (int k = 0; k < p2.second; k++) cout << p2.first << ' ';
			for (int k = 0; k < p1.second; k++) cout << p1.first << ' ';
		}
		else {
			for (int k = 0; k < p1.second; k++) cout << p1.first << ' ';
			for (int k = 0; k < p2.second; k++) cout << p2.first << ' ';
		}
	}
	else {
		auto p1 = stk.back(); stk.pop_back();
		for (int k = 0; k < p1.second; k++) cout << p1.first << ' ';
	}
}