오아시스 재결합( BOJ 3015 )

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

3015번: 오아시스 재결합

 

문제 파악하기

N명의 사람 중 서로를 볼 수 있는 사람이 총 몇 명인지 구하는 문제입니다. 서로를 볼 수 있다는 의미는 두 사람 사이에 어느 누구보다도 큰 사람이 없다는 의미입니다. 즉, 어느 한 사람만 볼 수 있는 경우는 제외해야 합니다. 예를 들어, 3명의 사람이 [ 6 5 4 ] 순서로 서있다고 가정해봅시다. 이 경우 가장 맨 앞의 사람(6)은 나머지 사람들(5, 4)을 볼 수 있지만, 반대로 맨 마지막 사람(4)은 맨 왼쪽의 사람(6)을 볼 수 없습니다. 이렇게 우리는 N명의 사람 중 2명을 골라서 사이에 큰 숫자가 있는지 확인해야 합니다. 이럴 때에는 항상 그렇듯이 중첩 반복문을 떠올리겠지만 입력되는 사람의 숫자가 최대 500,000명까지 될 수 있기에 정말 효율적인 알고리즘이 필요합니다.

 

문제 해결하기

효율적인 알고리즘을 위해서는 문제를 분석해야 합니다. 문제에서 원하는 상태는 N개의 숫자로 만들 수 있는 순서쌍 중 두 수 사이에 더 큰 숫자가 없는 경우의 수를 찾는 것입니다. 그렇다면 숫자를 확인할 때, 숫자들을 정렬된 상태를 유지하면 어떨까요? 정렬된 상태로 숫자를 확인하면 인접한 숫자들만 체크하면 되기에 문제가 훨씬 간단해집니다. 그리고 이 때, 스택을 사용하면 편하게 상태를 유지할 수 있습니다.

 

스택을 사용해서 숫자들을 내림차순으로 저장해보겠습니다. 내림차순으로 저장하는 이유는 자신보다 작은 값 중 인접한 값은 숫자쌍으로 만들 수 있기 때문입니다. 만약 현재 확인하는 숫자가 스택 내 가장 위의 값보다 크다면, 즉 내림차순이 아니라면 어떻게 해야 할까요? 그 경우에는 내림차순을 만족할 때까지 스택에 있는 값을 빼면 되며, 스택에서 값을 뺄 때에는 현재 값이 순서쌍을 만들 수 경우를 구해주면 됩니다. 만들 수 있는 순서쌍은 크게 3가지 측면에서 구할 수 있습니다. 첫 번째, 현재 들어올 값과 만들 수 있는 경우의 수를 구해줍니다. 두 번째, 지금 스택에 있는 가장 위쪽의 값과 만들 수 있는 경우의 수를 구해줍니다. 세 번째, 스택에 있는 동일한 크기의 숫자끼리 만들 수 있는 경우의 수를 구해줍니다. 이렇게 3가지 측면에서 확인하면 현재 스택에서 뺄 값이 만들 수 있는 모든 경우의 수를 구할 수 있습니다. 예시와 함께 같이 살펴봅시다. 만약 다음과 같이 6개의 숫자가 있다고 가정해봅시다.

 

6  6  6  5  2  5

 

참고로 스택에 숫자를 저장할 때에는 동일한 숫자는 한 번만 저장하되, 개수를 저장해주면 됩니다. 위의 경우, [ 6 ]이 연속으로 3개 있기 때문에 스택에서는 [ 6(3) ]과 같이 저장할 수 있습니다. 그 다음, [ 5 ]와 [ 2 ]는 각각 [ 6 ]과 [ 5 ]보다 작은 숫자이기 때문에 그대로 스택에 넣어줍니다. 이렇게 입력된 순서에 맞춰 내림차순으로 저장하면 모든 숫자는 오른쪽에 위치한 숫자들을 중 인접한 숫자들을 모두 확인할 수 있습니다. 문제는 스택에 [ 5 ]가 들어가려고 하는 경우입니다. 현재 스택에는 다음과 같이 숫자들이 들어있습니다.

 

[ stack ]   6(3)  /  5(1)  /  2(1)

 

여기서 [ 5 ]를 넣기 위해서는 스택에 이미 들어있는 [ 2(1) ] 값을 빼야 합니다. 왜냐하면 [ 2 ]는 지금 확인하는 [ 5 ] 때문에 오른쪽에 있는 숫자들은 더이상 확인할 수 없습니다. 따라서, [ 2 ]가 확인할 수 있는 모든 경우를 확인해주고 스택에서 제외해도 별다른 문제가 없습니다. 여기서 말하는 모든 경우는 바로 왼쪽과 오른쪽, 즉 위에서 말했던 스택에 들어있는 [ 5(1) ]와 만들 수 있는 경우(왼쪽)와 현재 들어올 [ 5(1) ]와 만들 수 있는 경우의 수(오른쪽)를 의미합니다. [ 2 ]는 딱 한 개만 있기 때문에 각각 1개씩 2개의 순서쌍을 만들 수 있습니다. 그리고 스택에서 제외해주면 됩니다. 그럼 이제는 스택의 가장 위쪽에는 [ 5(1) ]가 있습니다. 그리고 현재 들어갈 값은 [ 5 ]입니다. 따라서, 스택에 있는 [ 5(1) ]의 값을 [ 5(2) ]로 바꿔주면 됩니다. 그럼 스택의 값은 다음과 같이 변하게 됩니다.

 

[ stack ]   6(3)  /  5(2)

 

이렇게 모든 숫자를 확인하여 스택에 저장했으면 마지막으로 스택에 있는 값을 하나씩 제거하면서 만들 수 있는 모든 경우의 수를 구해주면 됩니다. 이 때에는 현재 스택의 가장 위쪽 값을 기준으로 같은 크기의 숫자들로 만들 수 있는 경우와 자신의 아래쪽에 위치한 숫자와 만들 수 있는 경우의 수를 구해주면 됩니다. [ 5(2) ]의 경우를 살펴봅시다. [ 5 ]는 총 2개 있기 때문에 1개의 숫자쌍을 만들 수 있으며, 2개의 [ 5 ]는 가장 오른쪽에 위치한 [ 6 ]과 함께 숫자쌍을 2개 만들 수 있습니다. 그리고 스택에서 제외하면 마지막으로 [ 6(3) ]만 남게 됩니다. [ 6(3) ]은 총 3개의 동일한 숫자가 있기 때문에 3개의 서로 다른 숫자쌍을 만들 수 있습니다. 그리고 스택의 마지막 값이기 때문에 이대로 종료하면 됩니다. 이렇게 스택을 사용하여 현재 숫자가 만들 수 있는 모든 숫자쌍을 만들면 원하는 결괏값을 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#define NMAX 500010
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> PAIR;
 
int N, t;
vector< lint > inp;
 
lint ret;
PAIR top;
stack< PAIR > st;
 
lint count(lint cnt) {
    lint ret = 0;
    
    // 키가 같은 사람끼리는 서로 볼 수 있음
    ret = cnt*(cnt-1)/2;
    
    // 왼쪽에 키가 더 큰 사람이 있다면 모두(cnt) 그 사람을 볼 수 있음
    if(!st.empty()) ret += cnt;
    
    return ret;
}
 
int main() {
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%d", &t);
        inp.push_back(t);
    }
    
    
    for(int i=0;i<N;i++) {
        while(!st.empty()) {
            top = st.top();
            
            if(top.first >= inp[i]) break;
            else {
                st.pop();
                
                // 현재 스택에 들어오는 사람은 top 모두(top.second) 볼 수 있음
                ret += top.second;
                
                // top이 볼 수 있는 왼쪽에 있는 사람 계산
                ret += count(top.second);
            }
        }
        
        if(st.empty() or top.first > inp[i]) st.push({inp[i], 1});
        else {
            st.pop();
            st.push({top.first, top.second+1});
        }
    }
    
    // 스택에 남은 값 처리하기
    while(!st.empty()) {
        top = st.top();
        st.pop();
        
        ret += count(top.second);
    }
    
    // 출력
    printf("%lld", ret);
}
 

후기

서로 볼 수 있다는 의미를 오해해서 한참을 돌아갔던 문제입니다. 문제를 꼼꼼히 읽어야 겠다는 걸 다시 한 번 느낀 문제였습니다. 스택을 연습할 수 있는 기본적인 문제라고 생각합니다.