백준 16496번 큰 수 만들기

🔒[문제 url]

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

🔑알고리즘

나열된 수가 커지기 위해서는, 앞자리 수가 커야한다.
우선순위 큐를 이용하여, 입력받을 때마다 큐 순서대로 나열했을때 앞자리가 커지도록 정렬해준다.

예를 들어 93 8가 입력된다면,
938 893중 큰 값은 938이므로, 큐에 93을 먼저 넣는다.
이 원리로 모든 수를 넣고, 큐의 원소를 차례로 출력한다.

🐾부분 코드

struct comp
{
	bool operator()(int a, int b)
	{
		string A = to_string(a);
		string B = to_string(b);
		return A + B < B + A;
	}
};

<우선순위 큐 정렬기준 설정>
숫자를 string type으로 입력받아, 앞자리 수가 커지도록 정렬되게끔 구현한다.

• Why string type?
  • 나열된 수가 int의 범위를 한참 넘어설 수 있다.
  • int 로 받을 경우, +의 의미가 나열이 아닌 덧셈이 된다.

void SOLVE()
{

	string ans = "";
	
	// 모두 0이면 0 출력
	if (!q.top())
	{
		cout << 0;
		return;
	}

	while (!q.empty())
	{
		ans += to_string(q.top());
		q.pop();
	}
	cout << ans;
}

<출력 부분>
큐의 첫 원소가 0이라면 모두 0이기 때문에, 0 하나를 출력하고 종료한다.
첫 원소가 0이 아니라면, 큐의 원소를 차례대로 나열하여 출력한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <string>
#include <algorithm>
// 자료 구조
#include <queue>
using namespace std;

struct comp
{
	bool operator()(int a, int b)
	{
		string A = to_string(a);
		string B = to_string(b);
		return A + B < B + A;
	}
};

int n;
priority_queue<int, vector<int>, comp> q;

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int number; cin >> number;
		q.push(number);
	}
}

void SOLVE()
{

	string ans = "";
	
	// 모두 0이면 0 출력
	if (!q.top())
	{
		cout << 0;
		return;
	}

	while (!q.empty())
	{
		ans += to_string(q.top());
		q.pop();
	}
	cout << ans;
}

int main()
{
	INPUT();

	SOLVE();
}

🥇문제 후기

이왜플..? 🤷🏻‍♂️