프로그래머스-스택 '탑'문제

https://programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

-스택문제라고 안적혀있었으면 스택으로 안하고 계산을해서 적었겠지..

사실 처음에는 스택이 어디 필요한가 했는데 출력형식때문에 스택이 필요했다.

나는 그랬다..

 

1. flag사용

  flag를 사용한 이유는 j==-1일때를 구분하기 위한것인데

  먼저 j=-1이 될때는 2가지 경우가 있다.

1. 배열을 다 돌았는데 i 보다 큰 탑이 없을때
2. 마지막을 돌았을때 그 마지막 i가 자신보다 높은 탑이었을 경우

이럴 경우 둘다 j=-1이 된다. 처음에는 두번째 상황을 고려하지 못해서 몇개의 테스트케이스를 실패햇다.

혹시 2,4,6번 테스트 케이스가 안된다면

테스트 케이스에 [5,4,3,2,1]을 넣고 [0,1,2,3,4]가 출력되는지 확인해볼것

 

=>그래서 이걸 구분하기 위해 flag를 넣었고 조건을 달아줬다.

 1번 경우에만 스택에 0을 넣도록 하였다. 

 

2. stack 사용

•    stack.pop()은 삭제의 의미
•  stack.top()이 출력/반환의 의미

이걸 잘 구분해야한다.

처음에는 pop 하면 반환된다고 생각해서 그렇게 출력하니 표기법에 오류가 났다.

그래서 top을 출력하고 출력후 pop을해 스택을 비웠다.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    stack<int> stack_top;
    int size=heights.size()-1;
    int stack_size;
    int flag=1;

     for(int i=size;i>0;i--){
          int j;
             for(j=i-1;j>=0;j--){
                 flag=1;
                if(heights[j]>heights[i]){
                   stack_top.push(j+1);
                   j--;
                   flag=0;
                   break;
                }
             }
              if(j==-1&&flag==1)
               stack_top.push(0);
     }
        stack_top.push(0);
        stack_size=stack_top.size();
         for(int i=0;i<stack_size;i++){
            answer.push_back(stack_top.top());
            stack_top.pop();
        }
    
    return answer;
}