[BOJ알고리즘, C++]#3015_오아시스 재결합, 스택

 

[BOJ알고리즘, C++]#3015_오아시스 재결합

 

BOJ 알고리즘 문제 풀이, 3015번 문제 "오아시스 재결합"

C++의 STL이 제공하는 stack 컨테이너를 활용하는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

1. 스택

[자료 구조]#0_선형 자료구조

 

[Basic C++] #64_stack

 

Details

 

• 스택은 LIFO(후입선출) 방식으로 동작하는 선형 자료구조입니다.
• 스택은 같은 구조와 같은 크기의 데이터를 정해진 한 방향으로만 삽입/삭제가 가능한 자료구조입니다.

 

2. 스택의 오름차순 정렬

[BOJ알고리즘, C++]#1725_히스토그램, 스택

 

[BOJ알고리즘, C++]#17298_오큰수, 스택

 

Details

 

• 먼저, 문제의 함정을 조심해야 합니다. 단순히, 배열을 차례대로 순회하며 현재 위치의 원소와 stack의 top을 비교하며 pop을 수행할 것인지 결정하는 문제가 아닙니다. 만약, 배열의 원소가 3개 이상 연속적으로 같은 값을 가질 경우 첫 번째 위치의 사람은 세 번째 위치의 사람이 보이지가 않습니다. 따라서, { 현재 위치의 값, 연속되어 나온 횟수 } 형식으로 pair를 만들어 stack에 삽입하고, 현재 위치의 값이 stack의 top.first 보다 클 경우, pop을 수행합니다. 그리고, 현재 위치의 값이 stack의 top.first와 같을 경우, 현재 위치의 값의 pair.second에 top.second를 전달하고, pop을 수행합니다. 
• 나머지는 스택을 오름차순으로 정렬하는 이전 문제들과 동일합니다.

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{

	int N;
	long long ans = 0;

    cin >> N;
    
	vector<long long> v(N);
	stack<pair<int, int>> s;
    
    for(int i=0; i<N; i++)
    {
        cin >> v[i];
    }

    for(int i=0; i<N; i++)
    {
        pair<int, int> p = make_pair(v[i], 1);
        while(!s.empty())
        {
            if(p.first >= s.top().first)
            {
                ans += (long long)s.top().second;
                if(p.first == s.top().first)
                    p.second += s.top().second;
                s.pop();
            }
            else
            {
                break;
            }
        }
        
        if(!s.empty()) ans++;
        
        s.push(p);
    }

	cout << ans << '\n';

	return 0;

}