1. 문제 소개

1262. Greatest Sum Divisible by Three

2. 나의 풀이

나머지가 1일때 가장 작은 두 개의 숫자와 나머지가 2일때 가장 작은 두 개의 숫자, 총 4개의 숫자를 추적했다.
총 합의 나머지가 1과 2일때를 나눠 최적의 숫자를 제거하는 방식으로 문제를 풀었다.
시간복잡도는 $O(n)$이다.

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        n = len(nums)                         # 배열 길이 (실제로는 사용되지 않지만 정보용 변수)
        ub = 10 ** 5                          # 초기 상한값(무한대 대용) — nums[i] 최대값보다 크거나 같은 값으로 설정
        mins = [[ub, ub], [ub, ub], [ub, ub]]
        # mins[r] = [가장 작은 값, 두 번째로 작은 값] (mod 3 == r 인 원소들에 대한 정보)
        # - mins[0]은 실제로 사용할 필요는 없지만, 인덱스 통일을 위해 함께 둔다.
        # - mins[1]: 나머지가 1인 수들 중 최소값 2개
        # - mins[2]: 나머지가 2인 수들 중 최소값 2개

        ans = 0                               # nums 전체 합을 누적할 변수

        for num in nums:                      # 모든 원소를 순회
            r = num % 3                       # 현재 숫자의 3으로 나눈 나머지
            if r != 0:
                # 나머지가 1 또는 2인 경우에만 mins를 갱신
                a, b = mins[r]                # 현재까지 기록된 (최소값, 두 번째 최소값)
                if num < a:
                    # num이 가장 작은 값이 되는 경우:
                    # 기존 가장 작은 a는 두 번째 최소값 b로 밀려난다.
                    b = a
                    a = num
                elif num < b:
                    # a보다는 크지만 기존 b보다는 작은 경우:
                    # 두 번째 최소값만 num으로 갱신.
                    b = num
                mins[r] = [a, b]              # 갱신된 (최소값 2개)를 저장
            ans += num                        # 전체 합을 누적

        # 이제 ans % 3 값에 따라 "얼마를 빼야 하는지"를 결정한다.
        if ans % 3 == 1:
            # 전체 합의 나머지가 1인 경우:
            #   1) 나머지 1인 수 하나를 빼거나
            #   2) 나머지 2인 수 두 개를 빼서 (2+2=4 ≡ 1 mod 3) 맞출 수 있다.
            remove1 = mins[1][0] if mins[1][0] != ub else ub
            # 후보1: mod 1 중 가장 작은 원소 1개 제거 (없으면 ub 그대로)
            remove2 = mins[2][0] + mins[2][1] if mins[2][1] != ub else ub
            # 후보2: mod 2 중 가장 작은 두 원소의 합 제거 (두 번째 최소값이 없으면 불가능)
            best = min(remove1, remove2)      # 둘 중 더 적게 빼는 쪽이 손실 최소
            return 0 if best == ub else ans - best
            # best == ub라면 양쪽 후보 모두 존재하지 않는다는 뜻 → 나머지를 0으로 맞출 수 없으므로 0 반환

        elif ans % 3 == 2:
            # 전체 합의 나머지가 2인 경우:
            #   1) 나머지 2인 수 하나를 빼거나
            #   2) 나머지 1인 수 두 개를 빼서 (1+1=2 ≡ 2 mod 3) 맞출 수 있다.
            remove1 = mins[2][0] if mins[2][0] != ub else ub
            # 후보1: mod 2 중 가장 작은 원소 1개 제거
            remove2 = mins[1][0] + mins[1][1] if mins[1][1] != ub else ub
            # 후보2: mod 1 중 가장 작은 두 원소의 합 제거
            best = min(remove1, remove2)      # 둘 중 더 적게 빼는 쪽 선택
            return 0 if best == ub else ans - best
            # 마찬가지로, 두 경우 모두 불가능하면 0 반환

        else:
            # ans % 3 == 0 인 경우:
            # 이미 3으로 나누어떨어지므로 전체 합 ans가 곧 최댓값이다.
            return ans

3. 다른 풀이

Editorial의 풀이는 다음과 같다.
시간복잡도는 $O(n\;\text{log}\,n)$이다.

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        # x % 3 == 0 인 값들은 아무 제약 없이 모두 더할 수 있으므로 따로 분리
        a = [x for x in nums if x % 3 == 0]

        # x % 3 == 1, x % 3 == 2 인 값들을 각각 큰 값부터 선택하기 위해 내림차순 정렬
        b = sorted([x for x in nums if x % 3 == 1], reverse=True)
        c = sorted([x for x in nums if x % 3 == 2], reverse=True)

        ans = 0                         # 부분집합의 최대 합(단, mod 3 == 0 조건 만족)을 저장
        lb, lc = len(b), len(c)         # b, c 리스트의 길이

        # b 리스트에서 선택할 개수를 (전체, 전체-1, 전체-2)로 제한적으로 시도
        # → mod 조건을 만족하기 위해 필요한 조합만 탐색하면 되기 때문
        for cntb in [lb - 2, lb - 1, lb]:
            if cntb >= 0:               # 유효한 개수일 때만 진행
                # c 리스트에서 선택할 개수도 동일한 방식으로 제한적 탐색
                for cntc in [lc - 2, lc - 1, lc]:
                    if cntc >= 0 and (cntb - cntc) % 3 == 0:
                        # (cntb - cntc) % 3 == 0 이면 b와 c에서 선택한 합이 mod 3 == 0이 됨
                        # b[:cntb], c[:cntc]는 "큰 값 우선"으로 선택된 상태
                        ans = max(ans, sum(b[:cntb]) + sum(c[:cntc]))

        # mod 0인 값들은 전부 더해도 안전하므로 마지막에 합산
        return ans + sum(a)

4. 마무리

그렇게까지 어렵지는 않은 문제여서 좋았다.