프로그래머스 문제 풀이 탑

문제 URL 탑

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이번에도 입력을 통해서 문제를 파악해보도록 하겠습니다. 첫 번째 입력입니다.

 

heights : [6, 9, 5, 7, 4]

 

여기서 각 송신탑들은 오른쪽에서 왼쪽으로 자신을 받아줄 송신탑들을 찾습니다. 자신 기준으로 왼쪽 탑들 중 첫 번째로 자신보다 큰 탑이 수신탑입니다.

 

어떻게 구할 수 있을까요? 먼저 직관적으로 한 번 풀어봅시다. heights의 인덱스를 1부터 시작해서 매기면 다음과 같을겁니다.

 

heights : [6, 9, 5, 7, 4]
indexes : [1, 2, 3, 4, 5]

 

5번째 탑(높이 = 4)에서 봤을 때 왼쪽 탑 중, 4번째 탑(높이 = 7)이 자신을 받아 줄 수 있습니다.

 

heights : [6, 9, 5, 7, 4]
indexes : [1, 2, 3, 4, 5]
answer  : [0, 0, 0, 0, 4]

 

4번째 탑(높이 = 7)에서 봤을 때 왼쪽 탑 중 2번째 탑(높이 = 9)이 자신을 받아줄 수 있습니다.

 

heights : [6, 9, 5, 7, 4]
indexes : [1, 2, 3, 4, 5]
answer  : [0, 0, 0, 2, 4]

 

3번째 탑(높이 = 5)에서 봤을 때 왼쪽 탑 중 2번째 탑(높이 = 9)이 자신을 받아줄 수 있습니다.

 

heights : [6, 9, 5, 7, 4]
indexes : [1, 2, 3, 4, 5]
answer  : [0, 0, 2, 2, 4]

 

2번째, 1번째 탑은 자신 왼쪽 기준으로 자신보다 높은 탑이 없으므로 받아줄 수 있는 탑이 없습니다. 따라서 결국 다음과 같게되겠죠?

 

heights : [6, 9, 5, 7, 4]
indexes : [1, 2, 3, 4, 5]
answer  : [0, 0, 2, 2, 4]

 

어떤 식으로 문제를 풀어야 하는지 감이 잡히시나요? 맞습니다. 이 문제는 오른쪽에서 왼쪽, 배열로 보면 뒤쪽에서 앞으로 이동하면서 계산합니다. 이런 문제들은 스택을 이용해서 풀면 편합니다.

 

스택을 이용해서 어떻게 풀 수 있을까요? 차근 차근 풀어봅시다. 먼저 가장 오른쪽 송신탑을 꺼내옵시다. 이를 top이라고 하겠습니다.

 

heights : [6, 9, 5, 7] // 4꺼내짐
top : 4
st : []
answer : []

 

이제 heights 맨 뒤부터 4보다 큰 원소를 찾습니다. 바로 7이 있군요. 이때, heights의 길이를 answer에 넣어줍니다.

 

heights : [6, 9, 5, 7]
top : 4
st : []
answer : [ 4 ] //현재 heights 길이 4

 

이제 맨 뒤의 원소 7을 꺼내옵니다.

 

heights : [6, 9, 5] // 7 빠짐
top : 7
st : []
answer : [ 4 ]

 

이제 7보다 큰 원소를 찾습니다. 5는 7보다 작기 때문에, heights에서 빼서 스택에 넣어줍니다.

 

heights : [6, 9] // 5 빠짐
top : 7
st : [ 5 ]
answer : [ 4 ]

 

이제 9가 보이는군요. 이 때 heights의 길이를 answer에 넣어줍니다.

 

heights : [6, 9]
top : 7
st : [ 5 ]
answer : [ 4, 2 ] //heights 길이 2

 

그리고 스택에 있는 높이들을 다시 heights에 넣어줍니다.

 

heights : [6, 9, 5] //st에 빠진 5가 들어옴.
top : 7
st : [ ] //5가 빠집니다.
answer : [ 4, 2 ]

 

이 과정을 heights가 빌 때까지 반복하면 됩니다. 그럼 결국 다음의 answer를 얻을 수 있습니다.

 

heights : [ ]
top :
st : [ ]
answer : [ 4, 2, 2, 0, 0 ]

 

스택을 이용했기 때문에 순서가 거꾸로 되어있습니다. 그래서 우리가 얻은 answer를 역으로 돌려주어야 합니다.

 

answer : [ 0, 0, 2, 2, 4 ]

 

이렇게 하면 정답을 구할 수 있습니다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

1. 스택 st를 생성합니다.
2. heights가 빌때까지 다음을 반복합니다.
   1. 먼저 heights의 가장 마지막 원소 top을 꺼내옵니다.
   2. heights가 비지 않으면서, 맨 뒤의 데이터가 top보다 작거나 같다면, 다음을 반복합니다.
      1. heights에 맨 뒤의 데이터를 꺼냅니다.
      2. 그 원소를 스택 st에 저장합니다.
   3. answer에 남은 heights의 길이를 저장합니다.
   4. st이 빌 때까지 스택의 원소들을 차례대로 꺼내어 다시 heights에 넣습니다.
3. 초기화된 answer를 거꾸로 돌립니다.

여기서 중요한 것은 heights를 스택으로 취급한다는 것입니다! 위의 알고리즘을 파이썬 코드로 표현하면 다음과 같습니다.

 

PYTHON 코드

def solution(heights):
    answer = []
    # 1. 스택 생성
    st = []
    
    # 2. heights 계산
    while heights:
        # 1. 맨 뒤 송신탑 꺼내옴.
        top = heights.pop()
        
        # 2. 현재 송신탑보다, 큰 송신탑이 나타날때까지 스택에 저장.
        while heights and heights[-1] <= top:
            st.append(heights.pop())
        
        # 3. 남아있는 길이를 asnwer에 저장
        answer.append(len(heights))
        
        # 4. 스택에 저장된 송신탑들을 다시 heights로 돌림
        while st:
            heights.append(st.pop())
    
    # 3. answer 역순으로 변환
    answer = answer[::-1]
    return answer
    

if __name__ == '__main__':
    heights = [6,9,5,7,4]
    result = solution(heights)
    print(result)

 

이번엔 CPP 코드입니다. 언어만 바뀐 것이지 알고리즘은 같습니다.

 

CPP 코드

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

#include <iostream>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    stack<int> st;
    
    while (!heights.empty()) {
        auto top = heights.back();
        heights.pop_back();
        
        while (!heights.empty() && heights.back() <= top) {
            st.push(heights.back());
            heights.pop_back();
        }
        
        answer.push_back(heights.size());
        
        while (!st.empty()) {
            heights.push_back(st.top());
            st.pop();
        }
    }
    
    reverse(answer.begin(), answer.end());
    return answer;
}

int main() {
    vector<int> heights = { 6, 9, 5, 7, 4 };
    vector<int> result = solution(heights);

    for (const auto & elem : result ) {
        cout << elem << " ";
    }
    cout << endl;

    return 0;
}