문제
https://www.acmicpc.net/problem/1422
문제이해
- K와 N을 입력한다. (1 ≤ K ≤ N ≤ 50)
- 둘째 줄부터 K개의 수(X)를 한 줄에 하나씩 입력한다. (1 ≤ X ≤ 1,000,000,000)
- N개의 수를 뽑아서 연결해 만들 수 있는 가장 큰 수를 출력한다.
문제를 해결하기 위해서는 수들을 특정 규칙에 따라 정렬해야 한다. 다음의 예시를 보자.
199 10
199와 10을 각각 한번 싹만 사용하여 만들 수 있는 수는 19910과 10199이고 이중 큰 수는 19910이다.
100 10
100과 10의 경우는 10010과 10100을 만들 수 있고 10100이 더 큰 수가 된다.
199 100 19
3개의 숫자를 각각 1개씩 이어 붙이는 경우는 19910019, 19919100, 10019919, 10019199, 19199100, 19100199가 있으며 여기서 가장 큰 수는 19919100이다.
3개의 숫자를 2개씩 묶어서 비교해 보자.
199와 100으로는 199100과 100199를 만들 수 있고 199100이 더 크다.
100과 19로는 10019와 19100을 만들 수 있고 19100이 더 크다.
199와 19로는19919와 19199를 만들 수 있고 19919가 더 크다.
순서로 따지자면 199 -> 19 -> 100 순서로 이어 붙일수록 더 큰 수가 나온다.
위의 예시들처럼 K개의 숫자를 각각 1번씩만 사용하여 큰 수를 만들기 위해서는 두 수끼리 있어 붙이기를 했을 때 큰 순서나 작은 순서대로 정렬하면 된다.
K개의 숫자들을 각각 1번씩만 사용하는 것이 아닌 여러 번 사용하는 경우는 어떨까?
간단하다. 우선순위가 가장 높은 수를 N - K번 있어 붙이면 된다.
199 100 19
3개의 숫자를 5번 이용하려고 한다. 이때 만들 수 있는 가장 큰 수는 19919919919100이다. 199가 나와야 할 부분에 199를 N - K번 출력해주기만 하면 된다.
다음은 위의 설명대로 만들어진 백준 1422번 숫자의 신 C++ 코드이다.
문제풀이
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main() {
int n, m, x;
cin >> n >> m;
vector<int> numbers(n);
for (int i{ 0 }; i < n; i++) {
cin >> numbers[i];
}
sort(numbers.begin(), numbers.end(), [](int a, int b) {
string strA = to_string(a);
string strB = to_string(b);
return strA + strB > strB + strA;
});
int maximumIdx{ 0 };
for (int i{ 0 }; i < n; i++) {
if ((static_cast<int>(log10(numbers[i]) + 1) > (static_cast<int>(log10(numbers[maximumIdx])) + 1))) {
maximumIdx = i;
}
else if ((static_cast<int>(log10(numbers[i])) == static_cast<int>(log10(numbers[maximumIdx])))) {
if (numbers[i] > numbers[maximumIdx]) {
maximumIdx = i;
}
}
}
for (int i{ 0 }; i < n; i++) {
if (i == maximumIdx) {
for (int a{ 0 }; a <= m - n; a++) {
cout << numbers[i];
}
}
else
cout << numbers[i];
}
}
sort를 이용하여 먼저 나와야 되는 순서대로 vector안의 원소들을 정렬하였다. 이후 우선순위가 가장 높은 원소를 찾고 해당 원소를 N - K번 출력하는 과정을 추가해주기만 했다.
문제후기
정렬법은 떠올리는데 크게 어렵지 않았으나 어떤 수를 여러 번 어느 곳에 출력해야 되는지 생각해야 되는 문제였다.
'Coding' 카테고리의 다른 글
[C++]백준 11726번: 2xn 타일링 (0) | 2023.08.01 |
---|---|
[C++]백준 11286번: 절댓값 힙 (0) | 2023.08.01 |
[C++]백준 17070번: 파이프 옮기기 1 (0) | 2023.07.25 |
[C++]백준 2178번: 미로 탐색 (0) | 2023.07.21 |
[C++]백준 7576번: 토마토 (0) | 2023.07.21 |