프로그래머스 문제 풀이 탑
문제 URL 탑
Contents
- 문제 지문 파악하기
- 구르미의 알고리즘 풀이
문제 지문 파악하기
이번에도 입력을 통해서 문제를 파악해보도록 하겠습니다. 첫 번째 입력입니다.
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 ]
이렇게 하면 정답을 구할 수 있습니다.
구르미의 알고리즘 풀이
"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.
- 스택 st를 생성합니다.
- heights가 빌때까지 다음을 반복합니다.
- 먼저 heights의 가장 마지막 원소 top을 꺼내옵니다.
- heights가 비지 않으면서, 맨 뒤의 데이터가 top보다 작거나 같다면, 다음을 반복합니다.
- heights에 맨 뒤의 데이터를 꺼냅니다.
- 그 원소를 스택 st에 저장합니다.
- answer에 남은 heights의 길이를 저장합니다.
- st이 빌 때까지 스택의 원소들을 차례대로 꺼내어 다시 heights에 넣습니다.
- 초기화된 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;
}