[코테연습] 1475. Final Prices With a Special Discount in a Shop

https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/description/?envType=daily-question&envId=2024-12-18

 

 

문제 타입

• 배열(Array): 주어진 배열을 순회하며 특정 조건에 따라 값을 계산합니다.
• 스택(Stack) (잠재적 개선): 특정 조건을 효율적으로 처리하기 위해 스택을 사용할 수도 있습니다.
• 구현(Implementation): 문제의 조건을 그대로 구현하는 유형입니다.

---

문제 분석

• 배열 prices에서 각 가격에 대해 이후 가격 중에서 자신보다 작거나 같은 첫 번째 값을 할인으로 적용.
• 할인 조건: 오른쪽에서 가장 먼저 나타나는 가격[j] ≤ 현재 가격[i].
• 결과: 할인 적용 후의 최종 가격을 구한 배열 반환.

---

문제 풀이

1. 문제 접근:
   • 현재 위치의 가격에서 오른쪽 부분만 확인하여 조건에 맞는 값을 찾음.
   • 조건에 맞는 값을 발견하면 할인 적용 후 결과 배열에 저장.
2. 구현 절차:
   • 배열의 각 요소를 순회 (O(n) 반복).
   • 각 요소마다 오른쪽 값을 탐색 (O(n) 반복), 따라서 총 시간복잡도는 O(n²).
   • 조건에 맞는 첫 번째 값을 발견하면 할인 적용.
   • 발견하지 못한 경우에는 원래 값을 결과에 저장.
3. 코드 구조:
   • 이중 반복문으로 구현.
   • 내부 반복문에서 조건 확인 후 값을 계산.
   • 계산된 값을 결과 배열에 저장 후 반환.
4. 개선 가능성:
   • 시간복잡도를 줄이기 위해 스택을 활용하면 효율적으로 문제를 해결 가능.
   • 스택을 사용하면 탐색 과정을 최적화하여 O(n) 복잡도로 변경 가능.

 

> java

 

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] result = new int[n];
        for(int i = 0; i < n; i++) {
            int p = prices[i];
            for(int j = i+1; j < n; j++) {
                if ( prices[j] <= prices[i] ) {
                    p = p - prices[j];
                    break;
                }
            }
            result[i] = p;
        }
        return result;
    }
}

 

 

> python

 

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        result = [0] * len(prices)
        for i in range(len(prices)) :
            result[i] = prices[i]
            for j in range(i+1, len(prices)) :
                if prices[j] <= prices[i] :
                    result[i] = prices[i] - prices[j]
                    break
        return result