문제 설명
prices라는 배열이 있고, prices[i]는 상점에서 i번째 상품의 가격을 나타낸다고 가정해 봅시다. 이 상점에서는 특별 할인 행사를 진행 중입니다. i번째 상품을 구매하면, j가 i보다 크면서 prices[j] <= prices[i]를 만족하는 최소 인덱스일 때 prices[j]만큼 할인을 받게 됩니다. 만약 그런 조건을 만족하는 j가 존재하지 않는다면 할인 없이 정가를 그대로 지불해야 합니다. 우리의 목표는 각 상품에 대해 특별 할인이 적용된 후 실제로 지불하게 될 최종 가격을 담은 배열을 구하는 것입니다.
예제로 이해하기
입력이 prices = [16, 8, 12, 4, 6]이라면 출력은 [8, 4, 8, 4, 6]이 됩니다. 각 상품별로 살펴보면 다음과 같습니다.
- 상품 0: 가격이 16이므로, 뒤에서 처음으로 등장하는 16 이하의 가격인 prices[1] = 8만큼 할인받아 최종 가격은 16 − 8 = 8이 됩니다.
- 상품 1: 가격이 8이므로, prices[3] = 4만큼 할인받아 최종 가격은 8 − 4 = 4가 됩니다.
- 상품 2: 가격이 12이므로, prices[3] = 4만큼 할인받아 최종 가격은 12 − 4 = 8이 됩니다.
- 상품 3과 4: 뒤쪽에 자신보다 낮거나 같은 가격의 상품이 없으므로 할인을 받지 못하고 각각 4와 6을 그대로 지불합니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- i를 0부터 prices 배열의 길이까지 반복합니다.
- j를 i+1부터 prices 배열의 길이까지 반복합니다.
- prices[i] >= prices[j]라면, prices[i]에서 prices[j]를 뺀 값을 저장하고 내부 반복문을 종료합니다.
- 조건을 만족하지 않으면 j를 하나 증가시키며 계속 탐색합니다.
- 모든 반복이 끝나면 할인이 적용된 prices 배열을 반환합니다.
Python 구현 예제
더 잘 이해하기 위해 다음 구현 예제를 살펴보겠습니다.
def solve(prices):
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
if prices[i] >= prices[j]:
prices[i] -= prices[j]
break
return prices
prices = [16, 8, 12, 4, 6]
print(solve(prices))입력
[16, 8, 12, 4, 6]
출력
[8, 4, 8, 4, 6]
복잡도 분석
시간 복잡도: O(n²) — 각 상품마다 뒤쪽에 있는 상품들을 순차적으로 확인해야 하기 때문입니다.
공간 복잡도: O(1) — 입력 배열을 직접 수정하여 결과를 저장하므로 추가 메모리가 거의 필요하지 않습니다.