개념
메서드
자바에서 Stack은 별도 클래스로 제공된다. 관련 메소드는 아래와 같다.
- empty : 스택이 비어있는지 여부를 boolean 으로 반환
- peek : top에 있는 객체를 반환 (꺼내지는 않음)
- pop : top의 객체를 읽고, 스택에서 꺼낸다
- push : 객체를 저장하고 이를 반환
- search : 인자로 전달 받은 객체의 위치를 반환. ( 0이 아닌 1부터 시작. 못찾으면 -1 )
스택의 활용
- 문자열 역순으로 정렬하기
- 괄호 검사하기
- 후위 표기법
괄호 검사하기
- 여러개의 괄호를 동시에 사용할때, 괄호의 종류와 열고 닫는 순서가 맞는다는 뜻
- 검사 방법 : 수식을 하나씩 돌면서 여는 괄호면 push, 닫는 괄호면 pop해서 괄호의 종류를 확인
괄호사용의 틀린예 3가지
- ( A + B ) * C )
- (( A + B ) * C
- { ( A + B } ) * C
열린 괄호 갯수 != 닫힌 갯수 인 경우는 스택에 괄호가 남아 있거나(>), Pop을 해야하는 상황에서 괄호가 없는(<) 경우이다.
스택에서 push, pop만큼이나 중요한 것이 스택이 비어있는지 이므로 코딩할때 신경써야한다.
후위표기법
컴퓨터가 계산할 수 있도록 표기하는 방법이다.
A + ( B * C )
후위표기법으로 표현하면 아래와 같다.
A B C * +
A B C 를 읽고 * 를 만나면 앞의 2 글자인 B C를 연산하고, + 를 만나면 이 계산 값과 앞의 1 글자를 읽어 연산한다.
스택을 활용하면, 피연산자를 만나면 push하고 얀산자를 만나면 앞의 2글자를 pop하여 연산한 뒤 결과를 다시 push하면 된다
문제 풀이
위의 활용에서 접근했던 방식과 다른 방향으로 풀어야하는 문제들이 오히려 많았다.
주식가격
문제
https://programmers.co.kr/learn/courses/30/lessons/42584
내 풀이 및 접근 방법
관점 차이임. 나는 현재 시점에서 미래 시점을 순회하며 작은 수가 있는지 확인.
스택을 사용하면 현재시점에서 과거시점을 순회하며 큰 수가 있는지 확인. 과거시점의 가격 지속시간을 계산함.
과거의 것은 계속 스택으로 쌓으면서 최신 것, 즉 peek 만 확인하면 되고, peek가 현재보다 크면 ( 현재 가격이 떨어진 것이면 ) peek(과거)의 지속시간 기록. 또 peek 뽑아서(pop) ( 더 과거 ) 현재보다 크면 내가 떨어진 시점인 현재와 비교해서 지속시간 기록.
즉, 내가 떨어진 시점인 과거의 시점을 찾아서 지속 시간 기록하기.
여기서 stack을 적용하는 포인트는,
비교해야할(혹은 기록해야할) 과거의 시점을 스택에 쌓고, 가장 최신의 과거 (peek)를 계속 확인하는 것.
기면 pop 아니면 본인을 push한뒤 다음
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
for(int i=0; i<prices.length; i++){
int price = prices[i];
int j = i+1;
int cnt = 0 ;
while(j!= prices.length ){
cnt++;
if(prices[j] >= price){
j++;
}else{
break;
}
}
answer[i]=cnt;
}
return answer;
}
}기능 개발
문제
https://programmers.co.kr/learn/courses/30/lessons/42584
내 접근 방법 및 코드
주식가격 문제의 관점을 적용하고자 했다.
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] answer ;
int[] time = new int[progresses.length];
ArrayList<Integer> deploy = new ArrayList<>();
//time
for(int i=0; i<progresses.length; i++){
int progress = progresses[i];
int speed = speeds[i];
time[i] = (100-progress)/speed;
// 빼먹어서 테스트 통과 못했던 부분
if((100-progress) % speed != 0){
time[i]++;
}
}
Stack<Integer> stack = new Stack<>();
int j = 0;
for(int i=0; i<time.length; i++){
if(i==0||stack.peek()<time[i]){
stack.push(time[i]);
deploy.add(1) ;
}else{
int cum = deploy.get(deploy.size()-1);
deploy.set(deploy.size()-1, cum + 1 );
}
}
answer = new int[deploy.size()];
int size=0;
for(int temp : deploy){
answer[size++] = temp;
}
return answer;
}
}
