[프로그래머스][JAVA] 주식 가격

💡 문제
주식 가격 (https://school.programmers.co.kr/learn/courses/30/lessons/42584)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

스택(Stack)은 프로그래밍에서 자주 사용되는 기본 자료구조 중 하나입니다. 스택은 LIFO(Last In, First Out) 원칙을 따릅니다. 즉, 마지막에 삽입된 요소가 가장 먼저 삭제되는 구조입니다. 스택은 다음과 같은 두 가지 주요 연산을 제공합니다

---

스택의 기본 동작

1. push: 스택의 맨 위에 요소를 추가하는 연산
2. pop: 스택의 맨 위에 있는 요소를 제거하고 반환하는 연산
3. peek: 스택의 맨 위에 있는 요소를 제거하지 않고 반환하는 연산
4. isEmpty: 스택이 비어 있는지 확인하는 연산
5. size: 스택에 있는 요소의 개수를 반환하는 연산

스택의 주요 특징

• LIFO 구조: 가장 나중에 들어간 요소가 가장 먼저 나옵니다.
• 한쪽 끝에서만 접근 가능: 스택은 요소를 추가하거나 제거할 때 항상 한쪽 끝(보통 'top'이라고 부름)에서만 연산이 이루어집니다.

스택의 사용 예

스택은 여러 가지 상황에서 유용하게 사용될 수 있습니다. 몇 가지 예를 들면:

• 함수 호출: 함수 호출이 스택 구조로 관리됩니다. 호출된 함수가 종료되면 호출 지점으로 돌아오기 위해 함수 호출 스택을 사용합니다.
• 괄호 검사: 소스 코드에서 괄호가 올바르게 닫혔는지 확인할 때 스택을 사용합니다.
• 역순 문자열 만들기: 문자열을 뒤집기 위해 스택을 사용할 수 있습니다.
• 탐색 알고리즘: 깊이 우선 탐색(DFS) 알고리즘에서 스택을 사용합니다.

Java에서 스택 사용 예제

Java에서는 java.util.Stack 클래스를 사용하여 스택을 쉽게 구현할 수 있습니다. 예제 코드는 다음과 같습니다:

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 스택 생성
        Stack<Integer> stack = new Stack<>();

        // 스택에 요소 추가 (push)
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 스택의 맨 위 요소 확인 (peek)
        System.out.println("Top element: " + stack.peek()); // 출력: 3

        // 스택에서 요소 제거 (pop)
        System.out.println("Popped element: " + stack.pop()); // 출력: 3
        System.out.println("Popped element: " + stack.pop()); // 출력: 2

        // 스택이 비어있는지 확인 (isEmpty)
        System.out.println("Is stack empty? " + stack.isEmpty()); // 출력: false

        // 스택의 크기 확인 (size)
        System.out.println("Stack size: " + stack.size()); // 출력: 1

        // 나머지 요소 제거
        System.out.println("Popped element: " + stack.pop()); // 출력: 1
        System.out.println("Is stack empty? " + stack.isEmpty()); // 출력: true
    }
}

스택의 동작 과정 설명

push 연산: 스택의 맨 위에 새로운 요소를 추가합니다.

stack.push(1); // 스택: [1]
stack.push(2); // 스택: [1, 2]
stack.push(3); // 스택: [1, 2, 3]

peek 연산: 스택의 맨 위에 있는 요소를 반환합니다(제거하지 않음).

int top = stack.peek(); // top: 3, 스택: [1, 2, 3]

pop 연산: 스택의 맨 위에 있는 요소를 제거하고 반환합니다.

int popped = stack.pop(); // popped: 3, 스택: [1, 2]
popped = stack.pop();     // popped: 2, 스택: [1]

isEmpty 연산: 스택이 비어 있는지 확인합니다

boolean empty = stack.isEmpty(); // empty: false

size 연산: 스택에 있는 요소의 개수를 반환합니다.

int size = stack.size(); // size: 1

 

스택 메서드 요약

peek() 메서드는 스택의 맨 위에 있는 요소를 반환하지만, 스택에서 제거하지는 않는 메서드입니다. 이를 통해 스택의 가장 최근에 추가된 요소를 확인할 수 있습니다. peek() 메서드는 요소를 제거하지 않기 때문에, 반복적으로 peek() 메서드를 호출해도 스택의 상태가 변하지 않습니다.

• push(E element): 스택의 맨 위에 요소를 추가합니다.
• pop(): 스택의 맨 위에 있는 요소를 제거하고 반환합니다.
• peek(): 스택의 맨 위에 있는 요소를 제거하지 않고 반환합니다.
• isEmpty(): 스택이 비어 있는지 여부를 확인합니다.

---

🤓 문제 풀이

주식 가격이 기록된 배열에서 각 시점별로 주식 가격이 떨어지지 않은 기간을 계산

이 문제는 스택을 사용하여 효율적으로 풀 수 있는 문제입니다. 스택을 사용하면 주식 가격이 떨어지는 시점을 쉽게 추적하고, 각 시점별로 가격이 유지된 기간을 계산할 수 있습니다. 스택의 LIFO 특성 덕분에 가격이 떨어지는 순간을 빠르게 감지할 수 있으며, 전체 시간 복잡도는 O(n)으로 유지됩니다.

즉 , 스택을 사용하여 가격이 떨어지지 않은 기간을 계산. 스택을 이용하면 중복된 비교를 줄일 수 있어 시간 복잡도를 최적화할 수 있습니다.

가격이 오르다가 떨어지는걸 제거하기 위해서 스택을 사용

---

import java.util.LinkedList;
import java.util.Queue;

public class Main {
   public int[] solutions(int[] prices) {
        // 결과를 저장할 배열
        int[] answer = new int[prices.length];

        // 가격과 인덱스를 저장할 스택을 초기화
        Stack<Integer> stack = new Stack<>();

        // 모든 가격에 대해 반복 (순차적으로 확인)
        for (int i = 0; i < prices.length; i++) {
            // 스택이 버이있지 않고, 현재 가격이 스택의 마지막 가격보다 작으면
            // 즉, 가격이 떨어졌다면
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                // 스택에서 인덱스를 꺼내고 해당 인덱스의 기간을 계산한다.
                int j = stack.pop();
                answer[j] = i - j;
            }
            // 현재 인덱스를 스택에 추가
            stack.push(i);
        }

        // 스택에 남아있는 인덱스들에 대해 남은 기간을 계산
        while (!stack.isEmpty()) {
            int j = stack.pop();
            answer[j] = prices.length - 1 - j;
        }

        return answer;

    }

}

---

📚 풀이 보완

코드 설명

결과 배열 초기화

• 각 주식 가격이 떨어지지 않은 기간을 저장할 배열을 초기화합니다.

 

int[] answer = new int[prices.length];

 

 

스택 초기화

• 주식 가격의 인덱스를 저장할 스택을 초기화합니다.

Stack<Integer> stack = new Stack<>();

 

주식 가격 배열 순회

for (int i = 0; i < prices.length; i++) {
    while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
        int j = stack.pop();
        answer[j] = i - j;
    }
    stack.push(i);
}

 

• 각 주식 가격을 순회합니다
  1. 조건 확인:
     • stack.isEmpty(): 스택이 비어 있지 않은지 확인합니다.
     • prices[i] < prices[stack.peek()]: 현재 가격 **prices[i]**가 스택의 맨 위에 있는 가격보다 작은지 확인합니다. **stack.peek()**는 스택의 맨 위에 있는 인덱스를 반환하며, 이를 통해 prices 배열에서 해당 시점의 가격을 가져옵니다.
  2. 스택에서 요소 제거 및 처리:
     • int j = stack.pop();: 조건이 만족되면 스택의 맨 위에 있는 인덱스를 제거하고 **j**에 저장합니다.
     • answer[j] = i - j;: 제거한 인덱스 **j**에서 현재 인덱스 **i**까지의 기간을 계산하여 answer 배열에 저장합니다.
  3. 스택에 현재 인덱스 추가:
     • stack.push(i);: 현재 인덱스를 스택에 추가합니다.
• 현재 주식 가격이 이전 주식 가격보다 낮아지는 경우:
  • 스택에서 인덱스를 꺼내고, answer 배열에 가격이 떨어지지 않은 기간을 저장합니다.
  • 예를 들어, **answer[j] = i - j;**는 인덱스 **j**에서 **i**까지의 기간을 계산합니다.
• 현재 인덱스를 스택에 추가합니다: stack.push(i);.

남은 인덱스 처리

while (!stack.isEmpty()) {
    int j = stack.pop();
    answer[j] = prices.length - 1 - j;
}

• 반복문이 끝난 후에도 스택에 남아있는 인덱스들은 끝까지 가격이 떨어지지 않은 경우이므로, 남은 기간을 계산합니다.
• 예를 들어, **answer[j] = prices.length - 1 - j;**는 인덱스 **j**부터 마지막 인덱스까지의 기간을 계산합니다.

주식 가격 문제를 스택으로 해결하는 이유

• 효율성: 스택을 사용하면 주식 가격이 떨어지는 순간을 빠르게 감지할 수 있습니다.
• 시간 복잡도: 각 주식 가격을 한 번씩만 처리하기 때문에 시간 복잡도는 O(n)으로 효율적입니다.
  • 시간복잡도가 O(n)이면, 이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다. 약식으로 충분히 큰 입력 크기에 대해서 수행시간이 입력 크기에 따라 선형적으로 증가함
• 직관적 접근: 주식 가격의 변화를 추적하고, 가격이 떨어지는 순간을 처리하는 것이 스택을 사용하면 직관적입니다.

스택을 사용하여 문제를 해결하면 효율적이고 직관적으로 주식 가격의 변화를 추적할 수 있습니다. peek() 메서드는 스택의 맨 위 요소를 확인하는 데 유용하며, 이를 통해 현재 가격과 비교할 수 있습니다.

📍 Plus+