[알고리즘] 크래프톤 정글 혼자 못 푼 문제 정리(탑 보기)

크래프톤 정글에서의 알고리즘 커리큘럼은 3주차까지만이다.

 

이후 문제들은 모두 C++로 풀었으며, 지금부터 정리할 알고리즘 글은 이후에 따로 알고리즘 스터디 중 혼자서 못 푼 문제들을 정리하는 글이므로 참고하길 바란다.

 

BOJ 22866 탑 보기

난이도 : (백준 난이도 기준) 골3

사용 알고리즘 or 자료 구조 : 스택

 

처음 생각한 풀이

시간 제한과 입력 값의 크기를 봤을 때 반드시 전체 순회 한, 두 번 만에 끝내야된다고 생각을 했다.

 

그래서 0번 인덱스 ~ N - 1번 인덱스까지 스택을 1개 이용하고, N - 1번 ~ 0번 인덱스까지 스택을 1개 이용하여 순회 두 번만에 끝낼 수 있을 것이라고 생각하여 계속 고민해봤지만 방법이 떠오르지 않아 구글링을 통해 접근법을 찾아보았다.

구글링 이후 풀이

혹시나 했지만 역시나 였다.

 

0번 ~ N - 1번을 순회 할 때에는 오른쪽 방향으로 가지만 눈은 왼쪽을 향해있다고 봐야한다.

 

또, 스택은 항상 아래에서부터 top까지 내림차순으로 숫자가 들어와있어야한다.

 

0번은 스택에 일단 넣어두고 시작을 하는데, 현재 인덱스의 높이가 스택의 top보다 크다면 현재 인덱스에서 스택 안에 있는 건물들을 못보는 것이므로 스택의 top이 현재 인덱스의 높이보다 커질 때까지 계속해서 pop을 해준다.

 

그렇게 되면, 현재 인덱스에서는 스택 안에 있는 건물들이 모두 보인다는 것이므로 스택의 size가 왼쪽을 향해 봤을 때 볼 수 있는 건물의 개수가 되는 것이다.

(여기서 왼쪽 방향으로 가장 가까운 건물의 인덱스가 스택의 top에 위치한 건물의 인덱스가 된다.)

 

오른쪽을 향해 봤을 때 보이는 건물의 개수도 방향만 다를 뿐 위와 동일하다.

 

 

두 번의 순회를 마친 뒤 나온 건물의 개수들을 합쳐주면 한 건물에서 볼 수 있는 건물들의 개수를 셀 수 있다.

 

또 각각의 방향에서의 가장 가까운 건물의 인덱스 값도 저장을 해놓으면 보이는 가장 가까운 건물의 인덱스도 같이 출력시킬 수 있다.

 

 

 

 

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

 

 

 

 

 

 

 

코드

#include <iostream>

#include <vector>

#include <stack>

#include <cmath>

#define INF 99999999

using namespace std;

int N;

vector<int> building(100000);

int main() {

    cin >> N;

    for(int i = 0; i < N; i++) {

        cin >> building[i];

    }

    vector<int> highNum(N, 0);

    vector<vector<int>> neareast(N, vector<int>(2, INF));

    stack<pair<int, int>> right;        // 건물 높이, 건물 인덱스

    right.push({building[0], 0});

    for(int i = 1; i < N; i++) {        // i 번째 건물 기준 왼쪽으로 볼 수 있는지 확인

        while(!right.empty() && right.top().first <= building[i]) {         // 만약 stack top 보다 현재 건물이 낮다면 볼 수 없는 건물이므로 pop, stack이 empty가 되면 while문 탈출

            right.pop();                                                    // pop하면 stack top부터 오름차순으로 건물이 들어가있음

        }

        if(!right.empty()) {

            neareast[i][0] = right.top().second;                            // stack이 비어있지 않으면 stack의 탑이 왼쪽으로 볼 수 있는 건물 중에 가장 가까운 건물

        }

        highNum[i] += right.size();                                         // stack에 남아있는 개수가 왼쪽으로 볼 수 있는 건물의 개수

        right.push({building[i], i});                                       // 현재 건물의 높이와 인덱스 push

    }

    stack<pair<int, int>> left;        // 건물 높이, 건물 인덱스

    left.push({building[N - 1], N - 1});

    for(int i = N - 2; i >= 0; i--) {                                       // 위와 동일하고 방향만 반대

        while(!left.empty() && left.top().first <= building[i]) {

            left.pop();

        }

        if(!left.empty()) {

            neareast[i][1] = left.top().second;

        }

        highNum[i] += left.size();

        left.push({building[i], i});

    }

    for(int i = 0; i < N; i++) {

        if(highNum[i] > 0) {

            cout << highNum[i] << " ";

            if(abs(i - neareast[i][0]) == abs(i - neareast[i][1]) || abs(i - neareast[i][0]) < abs(i - neareast[i][1])) {

                cout << neareast[i][0] + 1;

            }

            else{

                cout << neareast[i][1] + 1;

            }

        }

        else{

            cout << highNum[i];

        }

        cout << "\n";

    }

    return 0;

}