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

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

3015번: 오아시스 재결합

 

문제

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

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

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

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

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

 

풀이1 - 실패

(반례 알려줘.. 제발..)

 

처음에 시도한 나의 풀이..

input들을 벡터로 받고 이중 for문을 이용해서 풀었는데

자꾸 9% 에서 틀렸다고 나옴 ㅠㅠㅠ

 

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

using namespace std;

vector <int> input;
stack <int> s;
long long ans = 0;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    // 입력
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    
    // 계산
    for(int i=0; i<n; i++){
        s.push(0);
        for(int j=i+1; j<n; j++){
            if(s.top() > input[j]){
                break;
            }
            ans++;
            if(input[i] < input[j]){
                break;
            }
            s.push(input[j]);
        }
        while(!s.empty()) s.pop();
    }
    
    // 출력
    cout << ans;
    
    return 0;
}

 

아무튼 아무리 열심히 게시판을 뒤져봐도 안돼서..

다른 풀이로 간다

 

풀이 2

입력을 받는 동시에 스택에 넣으면서 계산하는 실시간 풀이

시간복잡도 면에서도 이게 더 낫다

다만 풀이가 조금. 많이. 복잡할뿐..

---

우선 모든 애들의 키가 다 다르다고 가정해서 간단하게 로직을 구성했다

테스트 케이스는 예제를 살짝 변형해서 "6 2 4 1 2 5 1" 을 넣어 답 7이 나오면 됨

 

// Authored by : seondal
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <stack>

using namespace std;

stack<int> s;
long long ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    while(n--){
        int h;
        cin >> h;
        
        // (2)
        while(!s.empty() && s.top().first < h){
            s.pop();
            ans++;
        }
        
        // (1)
        if(!s.empty()) ans++;
        s.push(h);
    }
   
    cout << ans;
    
    return 0;
}

/*
 */

 

로직을 설명해보겠다

 

차례대로 값을 입력받아서 스택에 넣으며 쌍을 만드는데,

입력값이 안에 있는 값과 접촉하면 하나의 쌍이 완성되는거라고 생각하면 편하다

(ex. top=2 일때 4를 넣으면 2와4 한쌍이 만들어짐)

 

그리고 한쌍이 완성될때마다 ans++;

 

(1)

그래서 비어있지 않은 스택에 값을 넣을때마다 ans++

스택이 비어있다면 만나는 애가 없으므로 쌍이 안만들어졌으니까 ans 증가시키지 않고 그냥 push

 

(2)

이때 넣으려는 값보다 꼭대기 값이 더 작다면 지금 넣으려는 애는 꼭대기 값 밑에 있는 애도 볼 수 있을거다

따라서 자신보다 작은 꼭대기값들을 while로 계속 꺼낼 (pop)건데,

이때 꺼내지는 애들도 다 지금 넣으려는 애와 쌍이 만들어지기 때문에 ans++

 

---

 

잘했으니 다음단계로 넘어가보자

키가 같은 애들이 있는경우, 그 애들은 하나로 취급한다. (중복을 인정하지 않음)

근데 계산을 해야하기 때문에 ans 카운트를 연속으로 중복된 애들 수 만큼 더해주는 방식으로 진행한다

연속으로 중복된 애들 수를 표현하기 위해 pair<int, int> 를 이용하여 첫번째는 키를, 두번째는 연속 중복 수를 표현하기로 했다.

 

(1) pop을 할때 ans를 하나씩 증가시키지 않고 꼭대기의 연속 중복 수 만큼 증가시킨다.

(2) 넣으려는 애와 꼭대기 애 키가 같다면,

(3) 들어가는 애는 자신과 같은 키의 애와의 쌍을 이루고 있으므로 꼭대기 애의 second 값을 ++ 해준다. (연속 중복 수 증가)

(4) 그리고 그 전에 자신과 같은 키인 애들과도 쌍을 이루므로 ans 를 연속 중복 수만큼 증가

(5) 근데 넣으면서 같은키들 뒤에 큰 키 하나가 있다면 걔랑 쌍을 이루므로 ans++;

 

// Authored by : seondal
// Co-authored by : -

//#include <bits/stdc++.h>
#include <iostream>
#include <stack>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    while(n--){
        int h;
        cin >> h;
        
        // (1)
        while(!s.empty() && s.top().first < h){
            ans += s.top().second;
            s.pop();
        }
        
        // (2)
        if(!s.empty() && s.top().first == h) {
            ans += s.top().second;  //(4)
            s.top().second++;  //(3)
            
            // (5)
            if(s.size() > 1) ans++;
            
            continue;
        }
        
        if(!s.empty()) ans++;
        
        s.push({h,1});
    }
   
    cout << ans;
    
    return 0;
}

/*
 */

 

끝!

내인생 첫 Gold1!!

수고했다!!!