문제 소개
다음과 같은 함수 정의가 있다고 가정해 보겠습니다.
def modify(arr, op, index):
if op == 0:
arr[index] += 1
if op == 1:
for i in range(len(arr)):
arr[i] *= 2이 함수는 두 가지 연산을 제공합니다. op가 0이면 지정된 인덱스의 요소를 1만큼 증가시키고, op가 1이면 배열의 모든 요소를 한꺼번에 두 배로 만듭니다.
우리가 해결해야 할 문제는 다음과 같습니다. 모든 요소가 0으로 초기화된 같은 크기의 배열에서 시작해 주어진 배열 nums와 완전히 동일한 상태를 만들려면, 이 함수를 최소 몇 번 호출해야 할까요?
예제로 살펴보기
예를 들어 입력이 nums = [1, 5, 3]이라면 결과는 7입니다. 초기 배열은 [0, 0, 0]이며, 다음 순서로 진행하면 목표 배열에 도달할 수 있습니다.
첫 단계에서 두 번째 요소를 1 증가 → [0, 1, 0]
두 번째 요소를 두 배로 만들기 → [0, 2, 0]
세 번째 요소를 1 증가 → [0, 2, 1]
배열의 모든 요소를 두 배로 만들기 → [0, 4, 2]
각 요소를 1씩 증가(여기서 총 3번의 연산) → [1, 5, 3]
따라서 총 3 + 4 = 7번의 연산이 필요합니다.
해결 접근 방법
이 문제의 핵심은 각 숫자를 거꾸로 분해하는 것입니다. 1을 더하는 연산은 개별 요소에 적용되지만, 두 배로 만드는 연산은 배열 전체에 한 번에 적용됩니다. 따라서 다음과 같이 생각할 수 있습니다.
증가 연산 횟수: 각 숫자를 이진수로 표현했을 때 1의 개수와 같습니다. 홀수에서 1을 빼면 짝수가 되므로, 홀수일 때마다 1을 빼는 연산이 필요합니다.
배수 연산 횟수: 배열 전체에 공통으로 적용되므로, 모든 숫자 중 가장 많은 배수 횟수가 필요한 값 하나만 계산하면 충분합니다.
구체적인 알고리즘은 다음과 같습니다.
ans := 두 요소가 모두 0인 배열 (ans[0]은 증가 연산 횟수, ans[1]은 최대 배수 연산 횟수)
nums의 각 n에 대해 다음을 반복합니다.
double := 0
n이 0이 아닌 동안 반복합니다.
n이 짝수이면: n := n / 2의 몫, double := double + 1
n이 홀수이면: n := n - 1, ans[0] := ans[0] + 1, ans[1] := max(ans[1], double)
ans의 모든 요소의 합을 반환합니다.
구현 예제
def solve(nums):
ans = [0, 0]
for n in nums:
double = 0
while(n):
if not n%2:
n = n//2
double+=1
else:
n-=1
ans[0]+=1
ans[1] = max(ans[1], double)
return sum(ans)
nums = [1,5,3]
print(solve(nums))입력
[1,5,3]
출력
7
복잡도 분석
각 숫자는 반복할 때마다 절반으로 줄거나 1이 감소하므로, 숫자 하나를 처리하는 데 O(log n)의 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N log M)(N은 배열의 길이, M은 최대값)이며, 추가로 사용하는 공간은 O(1)로 매우 효율적입니다.