문제 설명
숫자 배열(digits)이 하나 주어졌을 때, 주어진 숫자들을 원하는 순서대로 이어 붙여 만들 수 있는 가장 큰 3의 배수를 구하는 문제입니다. 결과값이 매우 커질 수 있으므로 반드시 문자열 형태로 반환해야 하며, 만들 수 있는 답이 존재하지 않으면 빈 문자열을 반환합니다.
예를 들어 입력이 [7, 2, 8]이라면 출력은 87이 됩니다.
핵심 아이디어
이 문제를 해결하는 열쇠는 3의 배수 판정법입니다. 어떤 수든 각 자릿수의 합이 3으로 나누어떨어지면 그 수 역시 3의 배수입니다. 따라서 다음과 같은 전략을 세울 수 있습니다.
모든 숫자를 내림차순으로 정렬한 뒤, 최대한 많은 숫자를 사용합니다.
자릿수의 합이 3으로 나누어떨어지지 않으면, 합을 3으로 맞추기 위해 가능한 한 영향이 적은 숫자(하나 또는 두 개)를 제거합니다.
각 숫자를 3으로 나눈 나머지(0, 1, 2)에 따라 세 개의 버킷으로 분류하면, 제거할 후보를 빠르게 찾을 수 있습니다.
알고리즘 단계
3개의 행을 가지는 2차원 배열 d를 정의합니다. d[i]에는 3으로 나눈 나머지가 i인 숫자들이 저장됩니다.
digits 배열을 내림차순으로 정렬합니다.
sum을 0으로 초기화합니다.
i가 0부터 digits의 크기 미만일 때까지 반복합니다.
x := digits[i]
d[x mod 3]의 끝에 digits[i]를 삽입합니다.
sum := sum + x 로 갱신한 뒤, sum := sum mod 3 을 적용합니다.
sum이 0이 아니라면:
d[sum]이 비어 있는 경우: rem := 3 - sum 을 구합니다. d[rem]의 크기가 2보다 작으면 빈 문자열을 반환하고, 그렇지 않으면 d[rem]에서 마지막 요소를 두 번 삭제합니다.
그 외의 경우: d[sum]에서 마지막 요소를 하나 삭제합니다.
ret을 빈 문자열로 초기화한 뒤, 세 개의 버킷에 남은 모든 숫자를 차례대로 이어 붙입니다.
ret을 내림차순으로 정렬합니다.
ret이 비어 있지 않으면서 첫 글자가 '0'인 경우 "0"을 반환합니다(남은 숫자가 모두 0인 경우). 그렇지 않으면 ret을 그대로 반환합니다.
배열이 내림차순으로 정렬된 상태에서 pop_back()을 호출하면 항상 가장 작은 숫자가 제거되므로, 결과값을 최대한 크게 유지할 수 있습니다.
예제 코드 (C++)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string largestMultipleOfThree(vector<int>& digits) {
vector<vector<int>> d(3);
sort(digits.begin(), digits.end(), greater<int>());
int sum = 0;
for (int i = 0; i < digits.size(); i++) {
int x = digits[i];
d[x % 3].push_back(digits[i]);
sum += x;
sum %= 3;
}
if (sum) {
if (!d[sum].size()) {
int rem = 3 - sum;
if (d[rem].size() < 2)
return "";
d[rem].pop_back();
d[rem].pop_back();
}
else {
d[sum].pop_back();
}
}
string ret = "";
for (int i = 0; i < 3; i++) {
for (int j = 0; j < d[i].size(); j++) {
ret += to_string(d[i][j]);
}
}
sort(ret.begin(), ret.end(), greater<int>());
if (ret.size() && ret[0] == '0')
return "0";
return ret;
}
};
main(){
Solution ob;
vector<int> v = {7,2,8};
cout << (ob.largestMultipleOfThree(v));
}입력
{7,2,8}출력
87