class Solution {
public int[] solution(int[] prices) {
int n = prices.length;
int[] answer = new int[n];
for (int i = 0; i < n; i++) {
int time = 0;
for (int j = i + 1; j < n; j++) {
time++;
if (prices[i] > prices[j]) {
break;
}
}
answer[i] = time;
}
return answer;
}
}이 문제는 이중 for문으로 문제를 풀게 될 경우 시간 복잡도는 O(n2)이 되고, prices의 길이 범위가 10만이므로 최악의 경우 100억, 약 100초의 시간이 시간이 소요하게 된다.
시간 복잡도 효율성 : O(1) >O(log n) > O(n) > O(n x log n) > O(n^2) > O(2^n)
시간 복잡도를 봐서도 나의 문제풀이는 많이 안좋은 편이다. 하지만 문제의 테스트 케이스가 없는 것 때문인지 몰라도 효율성 부분도 쉽게 통과되었다. 문제를 다 풀고나니 뭔가 이상함을 느꼇고 확인해 본 결과 나는 스택/ 큐를 사용하지 않고 문제를 풀었다. 그렇다면 스택과 큐로 문제를 풀어 보았다.
import java.util.Stack;
class Solution {
public int[] solution(int[] prices) {
int n = prices.length;
int[] answer = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
// 현재 가격이 스택의 꼭대기에 있는 가격보다 낮으면 가격이 떨어진 것이다.
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
int idx = stack.pop();
answer[idx] = i - idx;
}
stack.push(i);
}
// 스택에 남아있는 인덱스들은 끝까지 가격이 떨어지지 않은 경우이다.
while (!stack.isEmpty()) {
int idx = stack.pop();
answer[idx] = n - idx - 1;
}
return answer;
}
}스택의 특징
- 후입선출(lifo : Last In First Out) 구조 : 먼저 들어온 데이터가 나중에 빠져나가는 구조
- 단방햔 입출력 구조 : 데이터의 들어오는 방향과 나가는 뱡향이 같다.
- 데이터를 하나씩만 넣고 뺼 수 있다.
- 깊이 우선 탐색(DFS)에 이용된다.
스택의 관련 메서드
Push(E item) : 해당 item을 Stack이 top에 삽입
Pop() : Stack의 top에 있는 item을 삭제하고 해당 item을 반환
Peek() : Stack의 top에 있는 item을 삭제하지않고 해당 item을 반환
empty() : Stack이 비어있으면 true를 반환 하고 그렇지 않으면 false를 반환
search(Object o) : 해당 Object의 위치를 반환, Stack의 top 위치는 1, 해당 Object가 없으면 -1을 반환
코드 풀이
1. prices 배열의 길이 n을 구한다.
2. 결과를 저장할 배열 answer 를 n 길이로 초기화한다.
3. 첫 번째 반복문에서 prices 배열의 각 요소를 순회한다.
- 현재 가격이 스택의 TOP(peek)에 있는 가격보다 낮으면, 스택에서 인덱스를 꺼내어 가격이 떨어진 시점을 계산한다.
- 계산된 시점을 answer 배열에 저장한다.
- 현재 인덱스를 스택에 추가한다.
4. 반복문이 끝난 후, 스택에 남아있는 인덱스들은 끝까지 가격이 떨어지지 않은 경우다. 이 인덱스들에 대해 가격이 떨어지지 않은 기간을 계산하여 answer 배열에 저장한다.
문제의 포인트
문제를 보면 바로 생각난것이 이중 for문이다. 이중 for문을 사용하게 되면 시간 복잡도 O(n2)가 되면서 효율성이 매우 떨어지게 된다. 만약 데이터가 수천, 수백, 수만개 라고 하면 엄청나게 비효율적인 코드가 된다. 하지만 스택을 이용하여 문제를 풀면 시간 복잡도는 O(n)으로 이중 for문 보다 더 효율이 좋게 나오는것을 확인 할 수가있다.
코드를 작성하다보면 잘 동작 되는거 같아도 나중에 데이터가 쌓이고 나서 내가 작성한 코드가 효율성이 좋은지 확인해봐야한다. 코드 작성하는데 정답은 없다. 어떻게 코드를 작성하느냐에 따라 효율성이 좋고 나쁘고가 나오는데 우리는 이것을 해결을 해야한다.