[백준, C++] 1863 - 스카이라인 쉬운거

https://www.acmicpc.net/problem/1863

1863번: 스카이라인 쉬운거

 

문제 분석

문제 이름에 대놓고 쉬운거 라고 적어놨는데, 쉬운 거 치곤 난이도가 높다. 아마 스카이라인 안 쉬운거 가 있으니까 저런 이름이겠지 ? 라는 생각을 했다. 글만 읽어서는 문제가 이해되지 않았다. 다행히 문제 본문 아래에 힌트로 스카이라인을 표시해주면서 예제 테스트케이스가 어떻게 그런 결과를 출력하는지 보여준다.

한 건물을 다른 건물과 '다르다' 고 명확히 구별할 수 있는 기준은 높이가 뚝 떨어질 때이다. 이런 상황을 생각해보자.

 

..XX..
XXXX..
XXXXXX

 

이 경우, 건물이 최소한 3채이다.

 

1. 높이가 3인 건물

..33..
XX33..
XX33XX

 

2. 높이가 2인 건물

..XX..
2222..
2222XX

3. 높이가 1인 건물

..XX..
XXXX..
111111

 

이를 어떻게 파악할 수 있었을까 ? (당연히 나야 눈으로 ... 파악했다고 나중에 면접 코드리뷰에서 말하면 혼날 것 같다)

 

먼저 x좌표가 1-2인 구간을 보면 2층짜리 건물이 있다고 알 수 있다. 그 상태에서 x좌표가 3-4인 구간을 보면 3층짜리 건물이 있다고 알 수 있다. 마지막으로 x좌표가 5-6인 구간을 보면 1층짜리 건물이 있다고 알 수 있다. x좌표가 4에서 5로 변할 때, 스카이라인 높이가 3에서 1로 변했는데 우린 여기서 건물이 x좌표가 4인 구간까지 2개가 있음을 알아차려야 한다. 이를 어떻게 코드로 표현할 수 있을까 ?

 

코드

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

using namespace std;

int n;
int x, y;
struct Point {
    int x;
    int y;

    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }
};
vector<Point> vec;
stack<int> st;
int result;

void getInput();
void solve();
void printResult();

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        vec.push_back(Point(x, y));
    }
}

void solve() {
    vec.push_back(Point(x + 1, 0));

    for (Point p : vec) {
        while (!st.empty() && st.top() >= p.y) {
            if (st.top() > p.y) {
                result++;
            }
            st.pop();
        }

        st.push(p.y);
    }
}

void printResult() {
    cout << result << "\n";
}

 

코드 설명

문제를 풀기 위해 stack을 사용했다. 입력을 받아서 Point라는 구조체로 변환해 vector에 집어넣었고, 이 vector를 순차적으로 살펴보면서 문제를 해결했다. 문제의 핵심은 '높이가 변할 때'에 초점을 맞춰 살펴보는 것이다.

 

먼저 solve() 메서드의 첫 줄을 보면 Point(마지막 x좌표 입력값 + 1, 0)을 vector에 push_back한 것이 보일 것이다. 이는 엄연히 높이가 1인 건물과 지면은 다르기 때문에, 이를 구분하고자 추가로 넣은 것이다.

 

vector에 넣은 Point를 하나씩 가져와 건물의 개수를 파악할 것이다. stack이 비어있지 않고, stack의 top이 현재 보고 있는 Point의 y좌표보다 크거나 같으면 반복문을 실행하는데, 이 때 stack의 top이 y좌표보다 크면 건물이 있다고 카운팅한다. 그리고 반복문을 도는 동안은 stack의 top이 현재 보고있는 Point의 y좌표보다 크거나 같기 때문에, 스택에서 pop해준다. 반복문에서 탈출하면 현재 보고 있는 Point의 y좌표를 stack에 push한다.

 

풀이 자체는 쉬운데, stack을 사용한다는 개념을 떠올리기까지 한 5분 ... 정도 걸린 것 같다. 위에서 내가 든 예시처럼, 높이가 3에서 1로 뚝 떨어질 때 스택을 사용하지 않으면 단순하게 높이가 3인 건물에서 높이가 1인 건물로 변했네 ~ 정도만 인지할 수 있기 때문이다.

 

문제가 이름처럼 쉬운거는 아닌 것 같다.