99클럽(2기) - 코테스터디 25일차 TIL # Stack

LeetCode - 1475. Final Prices With a Special Discount in a Shop

You are given an integer array prices where prices[i] is the price of the ith item in a shop.

There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.

 

• j > i, prices[j] <= prices[i]를 만족하는 j의 최소값이 있으면 prices[i]를 prices[j]만큼 할인
• 없으면 기존 prices[i] 그대로 사용

---

 

1. 첫 번째 풀이

 직관적으로 이중 for문으로 풀었다. like 절차지향,,

 

1) 반환할 finalPrices를 담을 배열 초기화

 숫자 배열 finalPrices을 생성해준다.

 

2) 조건에 부합하면 할인 적용

 i는 0부터 prices 길이 -1까지, j는 i + 1부터 prices 길이 -1까지 순회한다. j 순회 전 j 순회 결과 할인이 적용되었는지 여부를 파악하기 위해 불리언 isDiscounted를 선언한다. j 순회 시 j > i, prices[j] <= prices[i]를 만족하는 j의 최소값이 있으면 finalPrices의 i번째 인덱스에 prices[i]를 prices[j]만큼 할인한 값을 추가한다. 최소값을 찾으면 더 이상 탐색할 필요가 없으니 isDiscounted를 true로 바꾸고 for문을 빠져나온다. 

 

 j의 순회가 끝났을 때 isDiscounted가 false이면 조건을 만족하지 못 한 것이므로 기존 prices[i] 그대로 finalPrices의 i번째 인덱스에 추가한다.

 

3) finalPrices 반환

 최종 할인 여부가 반영된 finalPrices 반환하면 끝!

class Solution {
    public int[] finalPrices(int[] prices) {
        int[] finalPrices = new int[prices.length]; // finalPrices를 담을 배열
        
        for (int i = 0; i < prices.length; i++) {
            boolean isDiscounted = false;
            // 할인 적용
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[i] >= prices[j]) {
                    finalPrices[i] = prices[i] - prices[j];
                    isDiscounted = true;
                    break;
                }
            }
            // 할인 미적용
            if (!isDiscounted) {
                finalPrices[i] = prices[i];
            }
        }

        return finalPrices;
    }
}

 

 

2. 두 번째 풀이

 첫 번째 풀이는 다소 비효율적이므로 for문을 한 번만 순회하고 Stack을 이용하는 방식으로 두 번째 풀이를 진행했다. java에서 Stack은 java.util.Stack을 import해서 Stack<type> stack = new Stack<>(); 이런 식으로 선언해서 사용한다. 

 

1) 반환할 finalPrices를 담을 배열, 다음 가격이 담겨있을 스택 초기화

 숫자 배열 finalPrices와 다음 가격이 담길 stack을 생성해준다. i는 무조건 j보다 작아야하기 때문에 i번째 price의 할인이 가능한지 판단할 때 stack에는 i보다 큰 위치에 있는 price만 담겨있으면 된다. 

 

2) 현재 가격보다 적은 가격이 있는지 탐색

 현재 가격보다 적은 가격이 나올 때까지 stack의 맨 위 요소를 pop한다. 모든 요소가 없어지면 while문이 종료된다.

 

3) 최종 가격 결정

 스택이 비어있지 않으면 자신보다 적은 가격을 찾은 것이므로 최종 가격은 현재 가격에서 해당 가격을 뺀 가격이다. 참고로, 최소 인덱스를 가지는 j가 공제할 가격이라는 조건이 있는데, stack을 이용하므로 가장 최소의 인덱스를 가진 값이 맨위에 위치하기 때문에 peek 하면 최소 인덱스 j의 값을 반환받을 수 있다.

 

 스택이 비어있으면 자신보다 적은 가격을 못 찾은 것이므로 최종 가격은 기존 가격과 동일하다.   

4) 현재 가격을 스택에 추가

 현재 가격을 스택에 추가해서 다음 i번째 price의 가격의 할인 여부를 판단하는 데 사용한다.

 

5) finalPrices 반환

 i가 0에 도달하여 for문 순회가 끝나면 최종 할인 여부가 반영된 finalPrices 반환한다!

import java.util.Stack;

class Solution {
    public int[] finalPrices(int[] prices) {
        int[] finalPrices = new int[prices.length]; // finalPrices를 담을 배열
        Stack<Integer> stack = new Stack<>(); // 현재 가격을 담을 스택
        
        for (int i = prices.length - 1; i >= 0; i--) {
            // 현재 가격보다 적은 가격 탐색
            while (!stack.isEmpty() && stack.peek() > prices[i]) {
                stack.pop();
            }
            
            // 최종 가격 결정
            if (!stack.isEmpty()) {
                finalPrices[i] = prices[i] - stack.peek();
            } else {
                finalPrices[i] = prices[i];
            }
            
            // 현재 가격을 스택에 추가
            stack.push(prices[i]);
        }
        
        return finalPrices;
    }
}

 

 

3. 새롭게 알게 된 점 / 느낀점

 스택을 사용하는 방법을 떠올리는 것 자체가 어려웠다. 문제를 푸는 데 있어서 어떤 자료구조가 가장 적합할지 판단하는 능력이 정말 중요한 것 같다.