[BOJ] 16496 큰 수 만들기

Table Of Contents

• 0. 들어가기
• 1. 문제 요약
• 2. 풀이 정리
• 3. 구현
• 4. 여담

0. 들어가기

• 문제 링크 : https://www.acmicpc.net/problem/16496
• 정답 코드 : http://boj.kr/c864554cb6c445ecb6d017b3875d0543

1. 문제 요약

음이 아닌 정수

이 수들을 나열해서 만들 수 있는 가장 큰 수를 출력한다.

2. 풀이 정리

• a와 b라는 숫자가 있다면, a+b가 더 큰지 b+a가 더 큰지 비교해볼 수 있다.
  • 30, 3이라는 숫자가 있다면 303보다 330이 더 크기 때문에 330을 만드는 쪽이 이득이다.
• 이렇게 모든 수를 차레로 정렬하면 된다.
  • 나는 버블 소트를 이용해서 정렬했다.
• 입력이 모두 0이어서 결과가 0000...처럼 나올 수 있다. 이런 경우는 0 하나만 출력하도록 예외 처리를 해 주자.

3. 구현

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

int N;
vector<string> S;

void bubbleSort()
{
	for (int i = N - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (S[i] + S[j] > S[j] + S[i])
			{
				string tmp = S[i];
				S[i] = S[j];
				S[j] = tmp;
			}
		}
	}
}

int main()
{
	cin >> N;
	S.resize(N);
	for (int i = 0; i < N; i++)
		cin >> S[i];

	bubbleSort();

	if (S[0][0] == '0')
	{
		cout << 0;
		return 0;
	}

	for (int i = 0; i < N; i++)
	{
		cout << S[i];
	}

	return 0;
}

4. 여담

• 예전에 풀었던 문제인가? 아이디어 자체는 빠르게 떠올랐는데 구현에서 3번 틀렸다.
  • a, b가 문자열이라서 그냥 a+b, b+a를 바로 비교하면 되는데 그걸 굳이 stoi나 stoll을 써서 런타임 에러가 발생했기 때문이다....
  • 정수가 1,000,000,000일 수도 있기 때문에 둘이 합치면 최대 10,000,000,001,000,000,000이나 되는 수가 나온다...!
• JS로 풀기 좋은 문제인 것 같다.