[BaekJoon 3015] 오아시스 재결합

안녕하세요. 오늘은 백준 3015번 오아시스 재결합이라는 문제를 알아보겠습니다.

 

해당 문제는

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

3015번: 오아시스 재결합

 

아래의 링크에서 확인하실 수 있습니다.

 

 

문제를 보시면, 시간제한이 1초이고, N의 범위가 500000입니다.

 

따라서 위 문제는 O(N^2)의 알고리즘으로 해결할 수 없으며,

기본적으로 현재를 기준으로 과거의 값을 돌아보는 형식의 로직이기 때문에 Stack을 사용하는 문제임을 추측할 수 있습니다.

 

또 한가지 주의하실 점은

 

만약에 500000개의 데이터가 모두 같은 숫자로 들어오면 어떻게 될까요?

그렇게 되면 서로 바라볼 수 있는 경우의 수는 50만 C 2가 되고, 이는 인트형의 범위를 훌쩍 넘어섭니다.

 

따라서 기본적으로 unsigned long long형 베이스나 long long형을 사용하셔서 결괏값을 표현하셔야 합니다.

 

우선 기본적으로 문제의 로직을 이해하기 위해 간단한 예시를 들어보겠습니다.

 

인풋 4 1 1 2가 들어왔다고 가정해볼게요.

 

1. 처음 4가 들어오면 앞선 사람이 아무도 없으므로 팝하고 비교할 것도 없습니다. 스택에 4를 넣어줍니다.

stack : 4

 

2. 그다음 1이 들어오면 앞선 4와 서로 마주볼 수 있습니다. 이때 1 이후에 들어오는 인풋에 대해서 4와 마주 볼 수 있는 경우의 수가 있을 수 있습니다. 따라서 현재 값보다 큰 4는 그대로 스택에 유지해줍니다.

stack : 4 1

 

3. 이제 2가 들어옵니다.

2가 1 다음으로 들어온 순간 1은 2 이후에 그 어떤숫자가 들어와도 서로 마주 볼 수 없습니다.

 

따라서

stack의 top에 위치한 원소보다 큰 원소가 새로운 인풋으로 들어오면, stack의 top은 더 이상 그 뒤의 원소와 고려할 사항이 없습니다. 따라서 이경우 1을 pop 해주면서, 1 보다 우선한 사람들과 바라볼 수 있는 경우가 몇가지인지 체크해주어야 합니다.

 

1은 4와 마주볼 수 있습니다. 따라서 stack을 pop 해주고, 결과에 1을 더해줍니다. 

4는 2보다도 큰 원소입니다. 따라서 2번 원칙과 같이 4는 그대로 스택에 유지해줍니다.

그리고 2를 스택에 push 해줍니다.

 

stack : 4 2

result : 1 {4, 1}

 

4. 같은 값인 2가 들어왔습니다.

여기서 문제가 복잡해집니다. 왜냐하면 그대로 stack에 푸시를 해주면 4 2 2가 되고, 이후에 3과 같이 2보다 큰 원소가 들어오면 앞선 2도 3과 마주할 수 있고 뒤에 있는 2도 3과 마주할 수 있습니다.

 

따라서 4 2 2에서 두개의 2가 이 문제의 결괏값을 세는데, 이후에 2보다 큰 원소에 대해서 같은 역할을 합니다. 

따라서 같은 원소가 들어오는 경우를 pair<int,int>를 사용하여 개수를 같이 포함해주겠습니다.

 

stack : {4,1} {2,2}

result : 1 {4, 1}

 

이제 3번 로직을 다시 보면

 

1은 4와 마주볼 수 있습니다. 따라서 stack을 pop 해주고, 결과에 1을 더해줍니다.

4는 2보다도 큰 원소입니다. 따라서 2번 원칙과 같이 4는 그대로 스택에 유지해줍니다.

그리고 2를 스택에 push 해줍니다.

 

여기서 stack을 pop해주고, 결과에 1을 더해주는 것이 아니라 pop 한 원소의 개수를 더해주시면 됩니다.

 

위의 로직을 바탕으로 소스코드는 다음과 같습니다.

 

#include <bits/stdc++.h>
using namespace std;

int n;
unsigned long long res;
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	
	stack<pair<unsigned long long, unsigned long long>> st;	
	for(int i = 0; i < n; i++) {
		unsigned long long tmp; cin >> tmp;
		pair<int,int> next = {tmp,1}; // 입력 받은 수와 갯수 1로 초기화 
		while(!st.empty()) {
			if(st.top().first <= tmp) {
				res += st.top().second;
				if(st.top().first == tmp) next.second = st.top().second+1; // 만약 동일한 원소라면 갯수 추가 
				st.pop();
			}
			else break;
		}
		if(!st.empty()) res++; // 위의 와일문을 끝냈음에도, stack이 비어있지 않다는 것은, 현재 인풋보다 큰 원소 존재 따라서 결과값 추가 
		st.push(next);
	}
	cout << res << endl;
	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.