[BOJ] 막대기

rany·2020년 11월 3일
0

Baekjoon Online Judge

목록 보기
5/10

✔️ 문제

😎 소스 코드

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int solution(vector<int> v, int n){
  stack<int> s;
  int answer = 0;
  
  for (int j = 0; j < n; j++) {
    if (s.empty() || v[j] < s.top()) {
      s.push(v[j]);
    } else {
      s.pop();
      while (!s.empty() && s.top() <= v[j]) {
        s.pop();
      }
      s.push(v[j]);
    }
  }
  
  answer = (int)s.size();
  cout << answer << endl;
  
  return answer;
}

int main() {
  int N, input;
  cin >> N;
  
  vector<int> v;
  
  // 각각의 막대기 높이를 입력받음
  for (int i = 0; i < N; i++) {
    cin >> input;
    v.push_back(input);
  }
  
  solution(v, N);
  
  return 0;
}

✊ 문제를 풀고 나서

  • 문제 접근
    1. 입력받은 각각의 막대기를 벡터 v에 push
    2. 스택 s에 v의 원소들을 하나씩 넣어주는데..
      2-1. 스택이 비었거나 현재 넣어주려는 값이 스택 top보다 작으면 push
      2-2. 그렇지 않으면? (현재 값이 top보다 크거나 같음) while 문으로 현재 값보다 top이 클 때까지 계속 pop해준다. 그 후 스택에 push
    3. 스택 사이즈가 answer
profile
개발개발

0개의 댓글