백준 3015: 오아시스 재결합

 

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

3015번: 오아시스 재결합

 

플래티넘 입문하기 좋은 문제다. 비슷한 느낌의 문제로 탑이 있다.

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

2493번: 탑

 

만약 오아시스 재결합을 풀다가 틀렸다면 아마 다음 세 이유 중 하나일 것이다.

 

1. 키가 같은 사람들끼린 서로 볼 수 있는데 그걸 생각 안 함

 

반례:

6

5 5 5 3 3 3

답: 9

 

2. 떨어져 있는 키가 같은 사람들끼리도 서로 볼 수 있는데 그걸 생각 안 함

 

반례:

5

2 2 1 2 2

답: 8

 

3. 정답은 int 범위가 아닐 수도 있음 ( 최대 50만 곱하기 50만이라 21억이 넘어갈 수 있다.)

 

 

 

 

풀이:

 

일단 이 문제는 스택을 이용해야 하는 문제다.

 

 

STEP 0.

 

문제의 예제 입력인

7
2 4 1 2 2 5 1

으로 설명을 해보겠다.

순서대로 사람의 이름을

A B C D E F G 라고 해보겠다.

 

count를 서로를 볼 수 있는 쌍의 수라고 해보자. 일단 count=0으로 시작한다.

 

첫번째 사람인 A의 키는 2이다.

일단 A를 스택에 넣는다.

현재 스택: A(2)

 

다음, B의 키는 4이다.

A와 B는 서로 볼 수 있다. (count: 1)

하지만 B가 A보다 키가 크기 때문에 B 오른쪽 사람들은 전부 A를 볼 수 없다. 그 사이를 B가 가로막기 때문이다.

 

그러므로 A가 볼 수 있는 사람은 더 이상 나오지 않는다. 그러므로 A를 스택에서 pop 한다.

그 후 B를 스택에 넣는다.

현재 스택: B(4)

 

다음, C는 B를 볼 수 있다. (count: 2) C는 B보다 작기 때문에 C는 B 왼쪽 사람들부터는 볼 수 없다. 그러므로 여기서 멈춘다. 또한, C 오른쪽 사람들도 B를 볼 수 있는 가능성이 있다. 그래서 스택에서 B는 pop하지 않고 C를 스택에 넣는다.

현재 스택: B(4) C(1)

 

이런식으로 왼쪽 사람부터 시작해서 진행해서 스택의 top에 있는 사람의 키와 비교한다.

 

그 다음차례는 D이다. 스택의 top에는 C가 있다. D와 C는 서로를 볼 수 있다. (count: 3) D가 C보다 크므로 D 오른쪽엔 C를 볼 수 있는 사람이 없다. 그러므로 C를 pop한다.

그 다음, 스택의 top에는 B가 있다. B와 D는 서로를 볼 수 있다. (count: 4) B가 D보다 크므로 D는 B 왼쪽 사람들은 볼 수 없다. 그리고 B를 pop하지 않는다.

그 후 D를 스택에 넣는다.

현재 스택: B(4) D(2)

 

다음은 E 차례다. E와 D를 비교해야 하는데, 두 사람의 키가 2로 같기 때문에 조금 복잡해진다. 

 

일단 E는 D를 볼 수 있다. (count: 5) 또, 둘이 키가 같으니 E는 D 왼쪽 사람도 볼 수 있다. 그러므로 일단 D를 pop하고 아까 과정을 진행한다. 그 다음, B는 E는 서로 볼 수 있고 (count: 6) B가 키가 더 크기 때문에 B를 pop하지 않고 E를 스택에 넣는다.

현재 스택: B(4) E(2)

그런데, 사실 D도 E 오른쪽의 사람들 볼 수 있다. 그러므로 실제로 스택은 

B(4) D(2) E(2) 가 되어야 맞다. 그래서 E를 스택에 넣기 전에 아까 pop한 D를 다시 스택에 넣어주는 작업을 해줘야 하는데... 이러면 시간복잡도가 너무 커진다. 이를 테면 입력이

500000

1 1 1 1 1 1 1 1 1 1 1 ...... 1 1 1 

이런 식으로 주어진다면?

매 사람마다 스택을 전부 비우고 다시 채우고 하는 작업이 필요해 시간복잡도가 O(n^2)이다. n이 최대 50만이라서 길어봤자 시간복잡도 O(nlgn) 안에는 풀어야 한다.

 

시간복잡도를 아끼기 위해 해야 하는 일이 있다. 바로 스택에 두가지 값을 저장하는 건데, 사람의 키와, 그 키를 가진 사람이 연속해서 몇명 있는지 이렇게 두 값이다. stack<pair<long long, long long>> 형태의 스택을 이용하는 것이다.

 

그래서 스택

B(4) D(2) E(2)

는

(4,1) (2,2)

처럼 나타내는 것이다. (키가 4인 사람이 1명, 2인 사람이 2명 있다는 뜻)

 

그렇기 때문에 E를 스택에 넣을 땐 지금까지 pop한 E와 키가 같은 사람의 수를 기억해 두었다가 pair의 두 번째 인수에 저장해 스택에 넣어야 한다.

 

다음, F의 키는 5이다.

스택의 top에는 키가 2인 사람이 2명 있다.

F는 그 둘 다 볼 수 있으니 count에 2를 더한다. (count: 8)

그 후 (2,2)를 pop한다. (F보다 키가 작으므로)

그 다음 스택의 top엔 (4,1)이 있다. 즉, 키가 4인 사람이 1명 있다.

F는 그 1명을 볼 수 있으니 count에 1을 더한다. (count: 9)

그리고 키가 5인 사람 1명 (F)를 스택에 넣는다.

현재 스택: (5,1)

 

마지막 차례 G는 스택의 top에 있는 키가 5인 사람 1명을 볼 수 있다.

그러므로 count에 1을 더한다. (count: 10)

 

모든 과정이 끝났고 count는 10이다. 따라서 10을 출력하면 된다.

 

 

 

헷갈릴 수 있으니 한 가지 상황만 더 설명해보겠다.

 

현재 스택: (5,3) (4,4) (3,2) 

상태인 경우를 가정해보자.

그리고 키가 4인 사람이 (P라고 부르자) 이 들어온다고 해보자.

일단 스택의 top엔 키가 3인 사람이 2명 있으니 count에 2를 더한 뒤 (3,2)를 pop한다.

그 다음 스택의 top엔 키가 4인 사람이 4명 있으니 count에 4를 더한 뒤 (4,4)를 pop한다.

그 다음 스택의 top엔 키가 5인 사람이 3명 있다. 하지만 P는 그 중 가장 오른쪽 사람만 볼 수 있다. 왜냐하면 그 왼쪽 사람들과 P는 중간에 P보다 키가 큰 사람(키가 5인 사람)이 서있기 때문이다. 그러므로 count에는 1을 더한다.

마지막으로, 아까 P와 키가 같은 사람 4명을 스택에서 지웠으니 스택엔 그 사람 4명에 P를 추가해 키가 4인 사람 5명 (4,5)를 넣어주어야 한다.

 

정리:

새로 입력받은 사람 P의 키가

1. 스택의 top에 있는 사람 N명보다 키가 크다면 count에 N을 더하고 스택에서 pop한다.

2. 스택의 top에 있는 사람 N명과 키가 같다면 count에 N을 더하고 스택에서 pop한다. 이 때 N값을 기억한다. (나는 plus라는 변수에 저장했다.)

3. 스택의 top에 있는 사람 N명보다 키가 작다면 count에 1을 더하고 과정을 멈춤.

4. 스택이 비었으면 과정을 멈춤

 

과정을 멈춘 뒤 스택에 P를 넣는데, 아까 P와 키가 같은 사람을 pop한 적 있다면 (P의 키, N+1)을 스택에 넣고 그런 적 없다면 (P의 키,1)을 스택에 넣는다.

 

다음은 C++로 구현한 것이다. 모든 사람은 최대 1번 pop당할 수 있기 때문에 시간복잡도는 O(n)이다.

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

typedef long long ll;
typedef pair<ll, ll> pll;


int main()
{
	int c;
	scanf("%d", &c);
	stack<pll> st;
	ll count = 0;
	
	for (int i = 0;i < c;i++)
	{
		int k;
		scanf("%d", &k);
		ll plus = 0;
		while (!st.empty())
		{
			if (st.top().first < k)
			{
				count += st.top().second;
				st.pop();
			}
			else if (st.top().first == k)
			{
				count += st.top().second;
				plus += st.top().second;
				st.pop();
			}
			else //st.top().first > k
			{
				count += 1;
				break;
			}
		}
		st.push(pll(k, 1 + plus));
		
	}
	printf("%lld", count);
}