[백준/BOJ] 30708 업&다운 C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/30708

[설명]

N개의 수 중 아무거나 하나를 잡고 이 수보다 큰 방향으로 더 이상 카드를 낼 수 없을 때까지 카드를 낸다. 반대쪽으로도 이를 해준다. 이후 이 수들을 돌면서 사이클(5 - 6 - 7 - 6 - 5 같은)을 모두 추가한다. 이후 최종 상태를 볼 때 만약 N개를 내지 못했다면 이는 불가능한 경우인 것이다.

[코드]

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

int n, arr[100001];
unordered_map<int, int> um;
vector<int> path, ans, ans2;

void find_path(int node) {
	um[node]--;
	int tf = 0;
	path.push_back(node);
	if (um.count(node - 1)) {
		if (um[node - 1] > 0) {
			find_path(node - 1);
			tf = 1;
		}
	}
	if (tf) return;
	if (um.count(node + 1)) {
		if (um[node + 1] > 0) {
			find_path(node + 1);
		}
	}
}

void update_path(int node) {
	int tf = 0;
	if (um.count(node - 1)) {
		if (um[node - 1] > 0) {
			um[node - 1]--;
			ans.push_back(node - 1);
			update_path(node - 1);
			tf = 1;
		}
	}
	if (tf) return;
	if (um.count(node + 1)) {
		if (um[node + 1] > 0) {
			um[node + 1]--;
			ans.push_back(node + 1);
			update_path(node + 1);
		}
	}
}

void update_path2(int node) {
	int tf = 0;
	if (um.count(node - 1)) {
		if (um[node - 1] > 0) {
			um[node - 1]--;
			ans2.push_back(node - 1);
			update_path(node - 1);
			tf = 1;
		}
	}
	if (tf) return;
	if (um.count(node + 1)) {
		if (um[node + 1] > 0) {
			um[node + 1]--;
			ans2.push_back(node + 1);
			update_path(node + 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int i, start; cin >> n;
	if (n == 1) {
		cin >> n;
		cout << n;
		return 0;
	}
	for (i = 1; i <= n; i++) {
		cin >> arr[i];
		start = arr[i];
		if (um.count(arr[i])) um[arr[i]]++;
		else um[arr[i]] = 1;
	}
	find_path(start);
	for (auto& iter : path) {
		ans.push_back(iter);
		int k = 0;
		if (um.count(iter - 1)) k += um[iter - 1];
		if (um.count(iter + 1)) k += um[iter + 1];
		while (um[iter] > 0 && k > 0) update_path(iter);
	}
	update_path2(ans[0]);
	if (ans.size() + ans2.size() != n) cout << -1;
	else {
		while (!ans2.empty()) {
			cout << ans2.back() << ' ';
			ans2.pop_back();
		}
		for (auto& iter : ans) cout << iter << ' ';
	}
}