[ 백준 3015] 오아시스 재결합 (C++)

3015번: 오아시스 재결합

 

 

문제!

---

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

 

 

---

이해하는 것에는 문제가 없었고 제가 생각하기에는 하나씩 넣어서 탐색해보면 되겠네? 라는 생각으로 코드를 짜버렸고

 

#include <iostream>
#include <algorithm>
#include<string>
#include <vector>
#include <stack>

using namespace std;

int n = 0;
int answer = 0;
int peo[500001]={0};

stack<int>st_memo;


int main() {

	

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> peo[i];
	}

	answer += n - 1;// 무조건 한쌍은 나옴

	int max_num = 0;

	for (int i = 0; i < n-1; i++) { // peo[i] 맨앞값

		
		max_num=peo[i + 1];// 일단 하나 넣기 // 한쌍
		for (int j = i+2; j < n; j++) {//한개씩 넣어보기 // 경우 작은값, 큰값, 같은값

			if (max_num > peo[i]) {
				break;
			}

			if (max_num == peo[j]) {
				answer += 1;
			}
			else if (max_num < peo[j]) {//최댓값보다 크다
				max_num=peo[j];
				answer += 1;
			}	
		}
	}
	cout << answer << endl;

	return 0;
}

 

답은 맞지만... 시간초과 나는 코드...

 

 

이 문제는 위 처럼 탐색이 아닌 스택을 이용한 탐색방법을 사용해야 풀수있는 문제라고 합니다..

 

저는 스택이라고는 생각 못했네요!

 

이에 블로그를 찾아보고 참고했습니다.

 

[C++] 백준 3015번 오아시스 재결합

 

풀이방법은 값을 받을때 부터 계속해서 현재값보다 큰지를 판단해서 쌍을 이룰지 못이룰지를 판단,

 

스택의 POP , PUSH를 통해 모든 부분을 탐색하는 방법...

 

 

 제 방법은 모든 구간을 탐색한다면

위의 새로운 방법은 되는지를 확인하면 끝이 나서 그 이후를 탐색 하지 않게 된다? >>> 좀더 줄일수 있겠네요

 

 

그럼 시작!

---

 

가장 먼저 입력을 받음과 동시에 탐색이 돌아갑니다.

for (int i = 0; i < n; i++) {
        cin >> height;

        // 큰 키 
        while (!s.empty() && height > s.top().first) { // 항시 돌아감
            ans += s.top().second;
            s.pop();
        }

 

물론 아직은 스택에 든게 없어서 2번째부터 돌겠네요

 

 

그리고 이 부분이 스택을 채워주는 부분!

if (s.empty()) { // 비어있고
            s.push(make_pair(height, 1));
        }
        else {/// 비어있지 않고
            if (s.top().first == height) {//키가 같으면
                int cur = s.top().second;
                s.pop();
                if (!s.empty()) {
                    ans++;
                }

                ans += cur;
                s.push(make_pair(height, cur + 1));
            }
            // 작은 키
            else {
                ans += 1;
                s.push(make_pair(height, 1));
            }
        }

스택이 비어있으면 넣어주고 비어있지 않다면 현재값부터 후의 값들과 비교를 해서 쌍을이룰수 있는지 탐색합니다!

 

이대로 출력하면 끝....

 

 

생각하기 어려운 문제였네요 약간 스택관련 문제만 꾸준히 풀었다면 풀었을것 같은문제..!!

 

더 분발하겠습니다

 

 

ALL

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

int n, height;
long long ans;
stack<pair<int, int>> s;

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


    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> height;

        // 큰 키 
        while (!s.empty() && height > s.top().first) { // 항시 돌아감
            ans += s.top().second;
            s.pop();
        }

       
        if (s.empty()) { // 비어있고
            s.push(make_pair(height, 1));
        }
        else {/// 비어있지 않고
            if (s.top().first == height) {//키가 같으면
                int cur = s.top().second;
                s.pop();
                if (!s.empty()) {
                    ans++;
                }

                ans += cur;
                s.push(make_pair(height, cur + 1));
            }
            // 작은 키
            else {
                ans += 1;
                s.push(make_pair(height, 1));
            }
        }
    }

    cout << ans;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!