[백준 1422번] - 숫자의 신 / C++

www.acmicpc.net/problem/1422

1422번: 숫자의 신

문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

-------------------------------------------------------------------------------------------------------------------

풀이

<C++>

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string arr[1001];
string arr2[1001];

bool Decending(string a, string b) {
	if (a.length() == b.length()) {
		return a > b;
	}
	return a.length() > b.length();
}

bool Decending2(string a, string b) {
	string A, B;

	A.append(a);
	A.append(b);
	B.append(b);
	B.append(a);

	return A > B;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int K, N;
	cin >> K >> N;

	for (int i = 0; i < K; ++i) {
		cin >> arr[i];
	}

	sort(arr, arr + K, Decending);

	for (int i = 0; i < K; ++i) {
		arr2[i] = arr[i];
	}
	for (int i = K; i < N; ++i) {
		arr2[i] = arr[0];
	}

	sort(arr2, arr2 + N, Decending2);

	string answer;

	for (int i = 0; i < N; ++i) {
		answer.append(arr2[i]);
	}

	cout << answer;

	return 0;
}

solved.ac 기준 플래티넘V 문제이다. 보통 기업의 코딩테스트 문제들이 골드수준이라고 들었는데, 이를 감안하면 상당히 어려운 난이도의 문제이다. 어떻게 풀지 구상하는 것은 크게 어렵지 않았으나, 정렬하는 과정이 개인적으로 힘들었다.

 

1. K와 N을 입력받는다.

2. arr 배열에 넣고 문자열의 길이가 내림차순이 되도록 정렬한다. 길이가 같은 경우, 사전식이 앞서는 문자열이 뒤로 가도록 정렬한다.

3. arr2 배열에 K개의 숫자들을 한번씩 우선 모두 넣고, N-K번 반복해서 추가해줄 가장 큰 수를 넣고 N크기의 배열을 완성한다.

4. arr2 배열의 문자열들이 합쳐졌을때, 더 큰 수가 앞으로 오도록 정렬하고 answer에 문자열을 하나씩 붙여준다.

5. answer를 출력한다.

 

이 문제를 푸는데 애를 먹은 이유가 바로 Descending2 때문이다. 맨처음 Decending을 아래와 같이 구현했었다.

bool Decending2(string a, string b) {
	return a > b;
}

하지만, 이 경우엔 K와 N이 5, 6이고 999, 909, 90, 9, 1의 입력을 받게되면, 9999999099091 이 출력이된다. 최댓값은 9999999909901 이기 때문에 차이가 발생한다. 한 자리의 숫자라도, 더 앞으로 보내게 되면 커지기 때문에 다른 정렬 법이 필요해서 아래와 같은 정렬을 구현했다.

bool Decending2(string a, string b) {
	string A, B;

	A.append(a);
	A.append(b);
	B.append(b);
	B.append(a);

	return A > B;
}

하지만, 이도 친구의 도움을 받아서 아래 처럼 간단하게 표현할 수 있었다.

bool Decending2(string a, string b) {
	return a+b > b+a;
}

이처럼 정렬을 구현할때는, 어떻게 bool type의 return값을 반환할 것 이냐에 신경쓰는 것이 중요한 것 같다.