💡 문제
주식 가격 (https://school.programmers.co.kr/learn/courses/30/lessons/42584)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
스택(Stack)은 프로그래밍에서 자주 사용되는 기본 자료구조 중 하나입니다. 스택은 LIFO(Last In, First Out) 원칙을 따릅니다. 즉, 마지막에 삽입된 요소가 가장 먼저 삭제되는 구조입니다. 스택은 다음과 같은 두 가지 주요 연산을 제공합니다
스택의 기본 동작
- push: 스택의 맨 위에 요소를 추가하는 연산
- pop: 스택의 맨 위에 있는 요소를 제거하고 반환하는 연산
- peek: 스택의 맨 위에 있는 요소를 제거하지 않고 반환하는 연산
- isEmpty: 스택이 비어 있는지 확인하는 연산
- 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);
}
- 각 주식 가격을 순회합니다
- 조건 확인:
- stack.isEmpty(): 스택이 비어 있지 않은지 확인합니다.
- prices[i] < prices[stack.peek()]: 현재 가격 **prices[i]**가 스택의 맨 위에 있는 가격보다 작은지 확인합니다. **stack.peek()**는 스택의 맨 위에 있는 인덱스를 반환하며, 이를 통해 prices 배열에서 해당 시점의 가격을 가져옵니다.
- 스택에서 요소 제거 및 처리:
- int j = stack.pop();: 조건이 만족되면 스택의 맨 위에 있는 인덱스를 제거하고 **j**에 저장합니다.
- answer[j] = i - j;: 제거한 인덱스 **j**에서 현재 인덱스 **i**까지의 기간을 계산하여 answer 배열에 저장합니다.
- 스택에 현재 인덱스 추가:
- 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+
'Algorithm > 코딩테스트' 카테고리의 다른 글
[프로그래머스][JAVA] 이중 우선순위 큐 (0) | 2024.05.26 |
---|---|
[프로그래머스][JAVA] 디스크 컨트롤러 (0) | 2024.05.26 |
[프로그래머스][JAVA] 다리를 지나는 트럭 (0) | 2024.05.23 |
[백준][JAVA] 비슷한 단어 (0) | 2024.05.22 |
[프로그래머스][JAVA] 베스트앨범 (0) | 2024.05.22 |