티스토리 뷰
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> heights) {
vector<int> answer;
stack<int> queue, temp;
int i;
for(i = 0; i<heights.size(); i++){
while(true){
if(temp.size()==0){
answer.push_back(0);
break;
}
if(heights[temp.top()] > heights[i]){
answer.push_back(temp.top()+1);
temp.pop();
break;
}
else temp.pop();
}
queue.push(i);
temp = queue;
}
return answer;
}
그냥 벡터를 순회하면 된다고 생각했다. 근데 스택/큐 문제였고, height의 길이가 길어지면 시간복잡도가 엄청나게 커져 시간초과가 발생할 것이라고 했다. 그래서 이왕 푸는거 스택/큐를 사용하고 싶었다.
heights의 0번부터 인덱스 값을 스택 queue에 담는다.
스택에 담기 전에 스택 temp 에 나보다 큰 수가 있으면 answer.push 한다.
나올 때 까지 temp.pop 한다.
만약 temp 스택이 다 빌때가지 없으면 그냥 answer.push(0) 한다.
queue에 새로 값을 넣고 temp 스택도 갱신한다.
왜냐면 while문 안에서 temp는 계속 바뀌니까
'알고리즘 > C++' 카테고리의 다른 글
[C++] 프로그래머스 프린터 (스택/큐) (0) | 2020.03.02 |
---|---|
[C++] 프로그래머스 쇠막대기 (스택/큐) (0) | 2020.03.02 |
[C++] 프로그래머스 멀쩡한 사각형 (0) | 2020.03.02 |
[C++] 프로그래머스 다리를 지나는 트럭 (스택/큐) (0) | 2020.03.02 |
[C++] 프로그래머스 다트게임 (0) | 2020.02.29 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- CellForRowAt 호출안됨
- pythonanywhere배포방법
- pythonanywhere배포
- Django
- UITableViewController Not Working
- Firebase 데이터베이스 추천
- iOS 데이터베이스
- 장고 게시판
- django pythoneverywhere
- 웹 배포
- Realtime Database
- 까만 화면
- CellForRowAt Not Called
- 데이터베이스 추천
- ModelForm Form 차이
- iOS UITableView 출력안됨
- python 웹 배포
- django 태그
- 알파벳 카운팅
- iOS 검은 화면
- cleaned_data
- 테이블출력안됨
- django clean
- iOS 화면 안나옴
- 장고 태그달기
- django 개발일지
- django 로그인접근
- django tag
- django 게시판
- 실시간 데이터베이스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
글 보관함