문제 개요
숫자로 구성된 리스트 target이 주어져 있다고 가정해 보겠습니다. 그리고 주어진 리스트와 길이가 같으며 모든 요소가 1로 채워진 리스트 X를 생각합니다. 우리는 다음과 같은 연산을 원하는 만큼 반복해서 수행할 수 있습니다.
- X에서 임의의 인덱스 i를 선택합니다.
- X[i]를 현재 X의 전체 합계 값으로 변경합니다.
목표는 이러한 연산을 반복하여 X를 target과 완전히 동일한 리스트로 만들 수 있는지 판별하는 것입니다.
예시로 이해하기
입력이 target = [5, 9, 3]이라면 출력은 True입니다. 변환 과정을 단계별로 살펴보면 다음과 같습니다.
- 초기 상태: X = [1, 1, 1], 현재 합계 = 3
- 합계 3으로 세 번째 요소 갱신 → X = [1, 1, 3]
- 현재 합계 = 5, 첫 번째 요소 갱신 → X = [5, 1, 3]
- 현재 합계 = 9, 두 번째 요소 갱신 → X = [5, 9, 3] = target ✔
풀이 접근 방식
정방향(1에서 시작)으로 시뮬레이션하면 매번 어떤 인덱스를 선택해야 할지 결정하기 어려워 비효율적입니다. 대신 역방향으로 사고하면 문제가 훨씬 단순해집니다. 마지막 연산에서 갱신된 값은 반드시 그 시점의 최대값이므로, target에서 가장 큰 값을 찾아 "갱신되기 이전 값", 즉 전체 합에서 자기 자신을 뺀 값으로 되돌리는 과정을 반복하면 됩니다.
여기에 나머지(modulo) 연산을 활용하면 같은 위치에서 여러 번 갱신이 연달아 일어나는 경우를 한 번에 처리할 수 있어 실행 속도가 크게 향상됩니다.
알고리즘 단계
- nums의 길이가 1이라면, 그 값이 1일 때만 True를 반환합니다.
- q := nums의 모든 숫자에 음수를 취한 큐를 생성합니다.
- q를 최소 힙(heap)으로 변환합니다. (음수로 저장하면 최대값을 빠르게 꺼낼 수 있습니다.)
- s := nums의 모든 숫자의 합
- ok := True
- ok가 True인 동안 다음을 반복합니다.
- x := 힙에서 요소를 꺼낸 뒤 음수 부호를 제거합니다. (현재 최대값)
- d := s - x (x가 갱신되기 이전의 전체 합)
- x2 := d > 1이면 x mod d, 그렇지 않으면 1
- s := s + x2 - x
- ok := x와 x2가 서로 다른지 여부
- x := x2
- -x를 힙 q에 삽입합니다.
- 반복이 끝난 후 q의 모든 요소가 -1이면 True를 반환합니다. (모든 값이 초기값 1로 되돌아왔다는 의미)
구현 예제
다음 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution: def solve(self, nums): if len(nums) == 1: return nums == [1] from heapq import heapify, heappop, heappush q = [-x for x in nums] heapify(q) s = sum(nums) ok = True while ok: x = -heappop(q) d = s - x x2 = x % d if d > 1 else 1 s += x2 - x ok = x != x2 x = x2 heappush(q, -x) return all(x == -1 for x in q) ob = Solution() target = [5, 9, 3] print(ob.solve(target))
입력
[5, 9, 3]
출력
True
핵심 포인트 정리
- 역방향 탐색: target의 최대값은 항상 마지막에 갱신된 값이므로, 이를 이전 값으로 되돌리며 검증합니다.
- 힙 활용: Python의 heapq에 음수 값을 저장해 최대값을 O(log n) 시간에 효율적으로 추출합니다.
- 모듈로 최적화: x mod d 계산으로 동일 위치의 반복 갱신을 한 번에 처리해 시간 복잡도를 크게 줄입니다.
- 종료 조건: 모든 요소가 1로 되돌아가면(-1이 힙에 가득 차면) target을 만들 수 있는 것으로 판단합니다.