[BOJ] 16496 큰 수 만들기
주어진 수들을 이어 만들 수 있는 가장 큰 수를 찾아봅시다
Table Of Contents
0. 들어가기
- 문제 링크 : https://www.acmicpc.net/problem/16496
- 정답 코드 : http://boj.kr/c864554cb6c445ecb6d017b3875d0543
1. 문제 요약
음이 아닌 정수(≤1,000,000,000)가 N(1≤N≤1,000)개 주어진다.
이 수들을 나열해서 만들 수 있는 가장 큰 수를 출력한다.
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로 풀기 좋은 문제인 것 같다.