[백준] 스카이라인 쉬운거 #1863

설명

이 문제를 보고 stack을 떠올릴 수 있다는게 부럽다...
처음에 감을 못잡아서 다른 사람의 풀이를 보고 스택으로 안풀고 그냥 hashmap으로 하면 되는거 아닌가해서 풀었는데 예제 testcase만 통과하고 나머진 실패했다.
hashmap을 사용한 풀이는 0을 만나기전까지 y값을 map에 담아 있으면 pass 없으면 넣어주고 count + 1해서 풀었었다. 이러면 다음의 문제가 생긴다.
22441122의 경우 빌딩은 2짜리, 4짜리, 1짜리, 2짜리로 총 4개지만 2에서 한 번 걸러져서 3개가 된다. 그래서 여기서는 stack을 사용해야 한다.
stack도 stack인데 여기서는 monotone stack이라는 기법이 이용된다.

stack을 하나두고 빌딩의 높이가 높아질 때마다 stack에 해당 높이를 추가하고 count를 +1 한다.
빌딩이 내려가면 내려간 높이만큼 stack에서 pop해줘야 내가 hashmap으로 풀 때 생기는 오류를 막아줄 수 있다.

뭔가 이런 문제는 코테에서 출제될 경우 풀어본 사람만 풀 수 있을 것 같은 느낌..

+그리고 다른 사람의 c++ 풀이를 보니 아래와 같은 기법도 배울 수 있었다.

for (auto &[x, y] : V) cin >> x >> y;

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const positions = input.slice(1).map((v) => v.split(' ').map(Number));

const solution = (N, positions) => {
  let count = 0;
  const stack = [];
  positions.forEach(([_, val]) => {
    while (stack.length && stack[stack.length - 1] > val) stack.pop();
    if (val && (stack.length === 0 || stack[stack.length - 1] < val))
      stack.push(val), count++;
  });
  return count;
};

console.log(solution(N, positions));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<pair<int,int>> V(N);
    for (auto &[x, y] : V) cin >> x >> y;
    
    stack<int> S;
    int cnt = 0;
    for (auto &[_, y] : V) {
        while(S.size() && S.top() > y) S.pop();
        if (y && (S.empty() || S.top() < y)) {
            S.push(y);
            cnt+=1;
        }
    }
    cout << cnt << '\n';
    return 0;
}