[백준] No.3015 - 오아시스 재결합 (C++, 스택)

문제

 

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

3015번: 오아시스 재결합

 

풀이

 

solved.ac 난이도: Gold 1

 

스택을 활용해서 푸는 문제. 해당 문제가 까다로운 이유는 아래와 같다.

문제에서는 A와 B의 사이에 키가 큰 사람이 없다면 서로 볼 수 있다.

즉, 사이에 키가 같은 사람이 껴있어도 서로를 문제없이 볼 수 있다.

현실적으로 눈의 위치가 얼굴의 중간쯤(?)에 있기 때문에 중간에 키가 비슷한 사람이 있다면 앞의 사람을 볼 수 없겠지만 해당 문제에선 이것이 가능하다..

 

키가 같은 사람이 없다면 아래와 같은 알고리즘으로 해결이 가능하다.

현재 사람의 키를 now라고 하고, 스택에는 키가 작은 순서대로 스택의 위쪽에 위치한다. (큰 순서대로 삽입되었다.)

 

1. stack.top < now

 현재 사람의 키가 스택의 top보다 크므로  now에 의해 가려져서, 현재 사람(now)의 뒤에 서있는 사람은 top을 볼 수 없다.

따라서 더 이상 스택에 담겨있을 의미가 없으므로 pop해주고, 쌍의 수(pair_num)을 1 증가시켜준다.

이를 스택에 더 이상 stack.top < now 인 경우가 없을 때까지 while문을 통해 반복해준다.

 

키가 같은 사람이 없다고 가정했기 때문에 while문을 통과했다 아래의 경우만 존재한다.(스택이 빈 경우는 제외)

 

2. stack.top > now

 이 경우에는 now는 stack.top 보다 앞쪽에 있는 사람은 볼 수 없다.

따라서 쌍의 수(pair_num)을 1 증가시켜준다.

 

이 과정이 끝났다면 now를 스택에 push해주자.

 

이러한 과정으로 스택은 키가 큰 순서대로 스택에 저장된다.

 

 

 

 

하지만 키가 같은 사람이 존재한다면,

5 2 2 3 3 4

와 같은 예제에서

 

6번째 사람은 앞의 5명을 모두 볼 수 있다.

5 2 2 1 3 3

 

따라서 stack<pair<int,int>>를 통해 first에는 키를, second에는 현재 스택에 같은 키를 가진 사람의 수를 기록하는 알고리즘을 작성하자.

 

1. stack.top < now

 현재 사람의 키가 스택의 top보다 크므로  now에 의해 가려져서, 현재 사람(now)의 뒤에 서있는 사람은 top을 볼 수 없다.

따라서 더이상 스택에 담겨있을 의미가 없으므로 pop해주고, 쌍의 수(pair_num)을 해당 키를 가진 사람 수만큼 증가시켜주자.

cnt_pair += st.top().second;

이를 스택에 더 이상 stack.top < now 인 경우가 없을 때까지 while문을 통해 반복해준다.

 

while문을 통과했다 아래의 경우만 존재한다.

 

2. stack.top == now

top가 같은 키를 같는다. now는 같은 키를 갖는 사람들과 모두 쌍을 지을 수 있다.

cnt_pair += st.top().second

만약 스택의 크기가 st.top().second 보다 크다면 키가 더 큰 사람이 스택에 저장돼있다는 것이므로 해당 사람과도 쌍을 지을 수 있다. 단 해당 사람은 now보다 키가 크기 때문에 cnt_pair는 1만 증가시켜 준다.

쌍의 수를 모두 늘려주었다면  now 같은 키를 가지는 사람을 +1로 업데이트 해주자.

 

3. stack.top > now

 top이 now보다 키가 크므로 top의 사람과만 쌍을 지을 수 있다.

cnt_pair는 1만 증가시켜 준다.

 

이 과정이 끝났다면

stack에 키와 사람 수 pair를 push해준다.

 

 

 

 

코드