프로그래머스 탑 (c++)

https://programmers.co.kr/learn/courses/30/lessons/42588

코딩테스트 연습 - 탑 | 프로그래머스

왼쪽으로 레이저 신호를 발사할 것이므로 신호를 송신할 탑보다 앞쪽 인덱스의 탑들을 검사해주면 된다.

앞쪽의 탑들 중 송신하는 탑보다 높은 탑이 있다면 그 탑의 인덱스를 스택에 넣어준다.

앞쪽의 탑들을 모두 검사했는데 송신탑보다 높은 탑이 하나도 없다면 0을 스택에 넣어준다.

 

가장 왼쪽에 있는 탑은 신호를 수신할 탑이 앞쪽에 없으므로 스택에 바로 0을 넣어주어서 따로 처리를 해준다.

그리고 다시 왼쪽에 있는 탑부터 수신 탑의 인덱스를 출력하기 위해서 스택에서 꺼낸 값들을 바로 answer에 넣어준다.

 

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
vector<int> solution(vector<int> heights) {
    
    vector<int> answer;
    stack<int> st;
    
    int size = heights.size();
    for(int i=size-1; i>0; i--) {
        bool flag = false;
        
        //왼쪽으로 레이저 신호를 발사
        for(int j=i-1; j>=0; j--) {
            if(heights[i] < heights[j]) {
                st.push(j+1);
                flag = true;
                break;
            }
        }
        
        //수신할 수 있는 탑이 하나도 없다.
        if(!flag) {
            st.push(0);
        }
    }
    
    
    //가장 왼쪽 탑
    st.push(0);
    
    while(!st.empty()) {
        answer.push_back(st.top());
        st.pop();
    }
    
    
    return answer;
}