정수 배열 nums가 주어졌다고 가정해 봅시다. 여기서 한 번의 이동(move) 연산이란 임의의 요소 하나를 선택하여 그 값을 1만큼 감소시키는 것을 의미합니다.
배열 A가 다음 두 조건 중 하나를 만족하면 지그재그(zigzag) 배열이라고 부릅니다.
- 모든 짝수 인덱스의 요소가 양옆의 인접 요소보다 큰 경우, 즉 A[0] > A[1] < A[2] > A[3] < A[4] > ... 와 같은 형태
- 모든 홀수 인덱스의 요소가 양옆의 인접 요소보다 큰 경우, 즉 A[0] < A[1] > A[2] < A[3] > A[4] < ... 와 같은 형태
우리의 목표는 주어진 배열 nums를 지그재그 배열로 변환하기 위해 필요한 최소 이동 횟수를 구하는 것입니다.
예를 들어 배열이 [1, 2, 3]이라면 정답은 2가 됩니다. 두 번째 요소인 2를 0으로 줄이거나, 세 번째 요소인 3을 1로 줄여서 지그재그 배열을 만들 수 있기 때문입니다.
문제 해결 접근 방법
이 문제는 짝수 인덱스를 높게 만드는 경우와 홀수 인덱스를 높게 만드는 경우, 두 가지 시나리오를 각각 계산한 뒤 더 작은 값을 선택하는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- solve()라는 메서드를 정의합니다. 이 메서드는 nums와 시작 인덱스 start를 매개변수로 받으며, 내부 동작은 아래와 같습니다.
- 필요한 연산 횟수를 저장할 변수 k를 0으로 초기화합니다.
- i를 start부터 nums의 길이까지 2씩 증가시키며 반복합니다.
- left : i - 1 < 0이면 100000(경계 밖 처리용 큰 값), 그렇지 않으면 nums[i - 1]
- right : i + 1이 배열 길이 이상이면 100000, 그렇지 않으면 nums[i + 1]
- temp : (left와 right 중 최솟값) - 1 - nums[i]
- temp가 음수라면, 현재 요소가 인접 요소보다 작아질 만큼 줄어야 하므로 k에 |temp|를 누적합니다.
- 반복이 끝나면 k를 반환합니다.
- 메인 메서드에서는 다음과 같이 처리합니다.
- ans = solve(nums, 0) — 짝수 인덱스를 피크로 만드는 경우
- ans = min(ans, solve(nums, 1)) — 홀수 인덱스를 피크로 만드는 경우와 비교하여 최솟값 선택
- ans를 반환합니다.
예제 코드 (Python)
더 나은 이해를 위해 다음 구현 예제를 살펴보겠습니다.
class Solution(object):
def solve(self,nums,start):
k = 0
for i in range(start,len(nums),2):
left = 100000 if i-1<0 else nums[i-1]
right = 10000 if i+1>=len(nums) else nums[i+1]
temp= (min(left,right)-1 - nums[i])
if temp<0:
k+=abs(temp)
return k
def movesToMakeZigzag(self, nums):
ans = self.solve(nums,0)
ans = min(ans,self.solve(nums,1))
return ans
ob = Solution()
print(ob.movesToMakeZigzag([1,2,3]))입력
[1,2,3]
출력
2
이 알고리즘은 배열을 한 번씩 두 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간도 상수 수준으로 매우 효율적입니다. 핵심 아이디어는 각 피크 위치의 요소를 인접한 두 요소 중 작은 값보다 1만큼 작게 만드는 데 필요한 감소량을 누적하는 것입니다.