'스택'으로 구현한 프로그래머스 탑(C++, 스택/큐)

프로그래머스 스택/큐 Level 2인 탑 문제에 대한 풀이입니다. 

 

문제 설명

수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

 

송신 탑(높이)는 왼쪽, 수신 탑(높이)는 오른쪽입니다.

5(4)	4(7)
4(7)	2(9)
3(5)	2(9)
2(9)	-
1(6)	-

맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• heights는 길이 2 이상 100 이하인 정수 배열입니다.
• 모든 탑의 높이는 1 이상 100 이하입니다.
• 신호를 수신하는 탑이 없으면 0으로 표시합니다.

이중 for문으로 구현하면, 간단한 문제이지만 스택/큐의 문제인만큼, 스택/큐를 사용해서 풀어보아요.

 

처음에 이중for문으로 금방 풀었는데, 스택/큐로 풀려니까 훨씬 더 오래 걸렸어요. 하하...

 

먼저, 이중for문으로 푼 것부터 보고, stack으로 풀면서 무엇이 달라졌는지 살펴볼게요.

맨 처음 직관적으로 푼 이중 for문 방식의 풀이입니다.

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    for(int i=0; i<heights.size();i++){//i+1값이 나와야 함
        bool isGet = false;
        for(int j=i-1;j>-1;j--){//자기바로 왼쪽부터 맨 왼쪽까지 탐색
            if(heights[i]<heights[j]){//j번째가 수신
                answer.push_back(j+1);
                isGet = true;
                break;
            }
        }
        if(!isGet){
            answer.push_back(0);
        }
    }
    return answer;
}

 이미 수신탑을 찾았으면 for문을 나오고, 그렇게 수신탑을 찾아서 중도에 반복문을 빠져나온 경우인지는 isGet을 통해 파악했습니다. isGet이 false이면 수신탑을 못 찾았다는 의미이니까 push_back(0);을 합니다.

 

이번엔 stack으로 구현할 거예요.

송신탑의 왼쪽에 위치한 원소를 모두 스택에 넣고, 송신탑보다 높으면 답을 적고, 낮으면 pop합니다.

이중for문과 달리 isGet변수가 필요없어요.

 

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    stack<int>tops;
    for(int i=0; i<heights.size();i++){
    
    	//송신탑의 왼쪽에 위치한 탑들을 모두 tops라는 스택에 추가
       for(int j=0; j<i;j++){
           tops.push(heights[j]);
       }
       
       //송신탑보다 작으면 pop하고 스택의 top원소를 갱신
       for(int j=tops.top();!tops.empty();j=tops.top()){
           if(j>heights[i]){
               answer.push_back(tops.size());
               break;
           }
           tops.pop();
       }
       
       //송신탑보다 높은 탑이 없거나 송신탑이 맨 왼쪽이라 그 탑보다 왼쪽인 탑이 없는 경우
       if(tops.empty()){
           answer.push_back(0);
       }
       
       //tops라는 스택 비워주기
       while(!tops.empty()){
           tops.pop();
       }
    }
    
    return answer;
}

 

송신탑보다 낮을 때마다 pop하면서 계속해서 j값을 스택의 top원소로 갱신해줍니다.

pop한 이후에 갱신하니까 수신탑을 찾지 못하면 계속 j값(스택의 top원소)이 변경되겠죠? 

 

[answer에 0을 push_back하는 경우]

스택에 남은 게 없다면, 탐색하는 동안 전부 다 송신탑보다 낮아서 pop되었다는거니까 수신탑이 없습니다.

또한, 제일 왼쪽에 있어서 자기보다 왼쪽에 있는 탑이 없으면 어차피 스택에 아무 원소도 안 들어가니까 이 경우도 스택에 남은 게 없는겁니다.

 

[answer에 답을 넣는 경우]

수신탑을 찾은 경우입니다. 즉, 송신탑보다 높은 원소가 top이 된 경우니까, 이 값의 인덱스를 가져오면 돼요. 그런데 어차피 이 값의 인덱스(0번째부터 시작하는 경우)는 [스택 사이즈-1]이니까, 문제에서 요구하는 것처럼 1부터 시작되는 인덱스를 answer 벡터에 넣으려면 그냥 스택의 size()를 벡터에 넣으면 됩니다.