반응형
재밌는 문제당
근데 처음엔 stack사용할 생각 못하고,
만약 높이가 5인 세 번째 탑이 들어오면 배열1~5까지 3으로 초기화하고,
그 후에 높이가 2인 네 번째 탑이 들어오면 배열 1~2까지는 4로 초기화하고,
다음에 높이가 7인 다 섯번째 탑이 들어오면 배열 1~7까지 5로 초기화
이런 식으로 풀어나가려 했다.
그러면 현재 탑의 높이를 배열의 인덱스로 바로 참조할 수 있으니까!
근데 탑의 높이가 1억까지 가능하고, 따라서 메모리 초과.
두 번째 생각한 방법은 스택을 사용하는 것이였다.
현재 들어온 탑의 높이가 스택안의 값보다 크면 pop하고 현재 값 push하기.
현재 들어온 탑의 높이가 스택안의 값보다 작으면 pop하지말고 그대로 push하기
근데 시간초과 나왔다 ㅠㅠ
그냥 다른 분 코드 보려고한다,,
http://kwanghyuk.tistory.com/57
시간 초과 내 코드
#include <iostream>
#include <stack>
using namespace std;
int top_height[500010] = { 0, };
int main() {
stack<int> s;
int n; //탑의 수
cin >> n;
// top_height[0] 에 엄청 큰 값 넣어두고
// stack 초기에 0 넣어둠.
// 그래서 다른 탑들이 다 높이가 낮으면 0에서 무조건 수신 받을 수 잇도록
top_height[0] = 987654321; // 최대값 INT_MAX
s.push(0);
for (int i = 1; i <= n; i++) {
int cur_height;
cin >> cur_height;
top_height[i] = cur_height; // 현재 값 저장
// 출력하기 위해서
// stack안의 값이 나의 높이보다 낮으면 다 없애기
while (top_height[s.top()] < cur_height) {
s.pop();
}
cout << s.top() << " ";
// stack 안의 값이 같을 수도 잇으니까 pop하고
// 그 후에 push 하기
while (top_height[s.top()] <= cur_height) {
s.pop();
}
// 안의 숫자가 더 크면 현재 값 push
s.push(i);
}
return 0;
}
반응형
