백준 3015번 오아시스 재결합

문제 링크입니다: https://www.acmicpc.net/problem/3015

 

시간복잡도를 O(N)으로 줄여야했기 때문에 어려웠던 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 을 저장하는 스택을 선언합니다.

2. 핵심은 스택 제일 아래 저장되어 있는 키부터 top까지 내림차순을 유지하는 것입니다.

-> 따라서, 현재 키가 스택의 top보다 클 경우 스택의 top이 현재 키와 같거나 클 때까지 pop을 해줍니다.

3. 스택이 비어 있다면 스택에 push 해줍니다.

4. 스택이 비어 있지 않을 경우

i) 현재 키와 스택의 top이 같을 경우 pop을 해준 뒤 second(연속 몇 명)를 수정해줍니다.

-> 이 때, 스택이 비어있지 않다면 스택 내 제일 큰 사람과 쌍을 이루므로 결과에 1 증가

ii) 현재 키가 스택의 top보다 작을 경우 스택에 push를 해주고 스택 내 자신보다 처음으로 큰 사람과 현재 키가 쌍을 이루기 때문에 결과를 1 증가시킵니다.

5. 반복문이 끝나면 누적 결과를 출력해줍니다.

 

#include <iostream>

#include <stack>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        stack<pair<int, int>> s; //키, 연속 몇 명

 

        long long result = 0;

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

        {

                 int height;

                 cin >> height;

 

                 //현재 사람의 키가 스택의 top에 있는 사람보다 크다면

                 //이 사람은 현재 사람 이후로 쌍을 이루지 못함

                 while (!s.empty() && s.top().first < height)

                 {

                         result += s.top().second;

                         s.pop();

                 }

 

                 //맨 앞에 사람을 세운다()

                 if (s.empty())

                         s.push({ height, 1 });

                 else

                 {

                         //같은 키의 경우 따로 처리

                         if (s.top().first == height)

                         {

                                 pair<int, int> cur = s.top();

                                 s.pop();

 

                                 result += cur.second;

                                 //스택 내 제일 큰 사람과 쌍을 이룸

                                 if (!s.empty())

                                          result++;

 

                                 //연속해서 같은 키가 나오므로

                                 cur.second++;

                                 s.push(cur);

                         }

                         //더 작은 사람이 왔을 경우

                         else

                         {

                                 s.push({ height, 1 });

                                 //스택 내 제일 큰 사람과 쌍을 이룸

                                 result++;

                         }

                 }

        }

 

        cout << result << "\n";

        return 0;

 

}

개발환경:Visual Studio 2017

 

 

 

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~