Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 숫자 배열에서 만들 수 있는 3의 가장 큰 배수 구하기

문제 개요

0부터 9 사이의 숫자들이 담긴 배열이 주어졌을 때, 이 숫자들 중 일부를 골라 임의의 순서로 이어 붙여 만들 수 있는 수 중에서 3의 배수이면서 가장 큰 값을 찾는 것이 목표입니다. 결과값이 매우 커질 수 있으므로 문자열 형태로 반환해야 하며, 만들 수 있는 3의 배수가 존재하지 않는다면 빈 문자열을 반환합니다.

예를 들어 입력이 [7, 2, 8]이라면, 출력은 87입니다.

접근 방법

이 문제는 각 숫자를 3으로 나눈 나머지를 기준으로 분류하는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 어떤 수가 3의 배수인지 판단하려면 각 자릿수의 합이 3으로 나누어떨어지는지만 확인하면 되기 때문입니다. 따라서 전체 자릿수의 합을 3으로 나눈 나머지에 따라, 특정 나머지를 가진 숫자를 하나 또는 두 개 제거하면 전체 합을 3의 배수로 만들 수 있습니다.

알고리즘 단계

  • 나머지 0, 1, 2에 해당하는 숫자를 저장할 세 개의 행을 가진 2차원 배열 d를 정의합니다.
  • 숫자 배열을 내림차순으로 정렬합니다.
  • 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 := 빈 문자열로 초기화합니다.
  • i := 0부터 2까지, j := 0부터 d[i]의 크기까지 반복하며 ret에 d[i][j]를 문자열로 이어 붙입니다.
  • ret을 내림차순으로 정렬합니다.
  • ret이 비어 있지 않고 ret[0]이 '0'이라면 "0"을 반환합니다.
  • 그렇지 않으면 ret을 반환합니다.

예제 코드 (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

정리

이 알고리즘은 숫자를 나머지별로 분류한 뒤, 전체 합이 3의 배수가 되도록 최소한의 숫자만 제거하기 때문에 결과적으로 가능한 한 많은 숫자를 남겨 가장 큰 수를 만들 수 있습니다. 시간 복잡도는 정렬이 지배적이며 O(n log n), 공간 복잡도는 O(n)입니다.