[3015] 오아시스 재결합

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

3015번: 오아시스 재결합

스택을 활용한 문제다. 

 

풀이

입력되는 모든 키를 비교하게 되면 당연하게도 시간초과가 일어난다. 풀이를 찾아보니 스택을 사용한다면 O(N) 만에 탐색이 가능했다.

우선 주어지는 현재 키를 순서대로 스택에 담아낼 것이다. 

(키 높이, 인원)를 담는 비열을 생성하여 현재 주어진 키와 스택의 top과 비교하여 쌍을 계산하면 된다. 

 

스택이 비어있다면 당연하게도( 현재 키 높이: 인원(1) )을 담고 다음 정보를 입력받는다.

 

크게 두 가지 경우로 나뉜다.

1. top의 키높이가 현재 키높이와 같은 경우  -> top의 인원수만큼 쌍으로 추가

 

2. top의 키높이보다 현재 키높이가 큰 경우 -> 인접한 경우이므로 쌍으로 추가

 

위 두 가지 경우는 top의 키높이가 현재 키높이보다 클 때까지 혹은 스택이 빈상태가 될 때까지 pop 연산을 수행한다.

 

pop 연산을 수행한 이후에 스택이 비어있지 않다면 top에 해당하는 키와 현재 키와는 인접한 경우이므로 쌍으로 추가할 수 있다.

 

키높이가 같은 경우를 거쳤다면 (현재 키높이 : 추가했던 인원수+1) 형태로 스택에 추가.

그렇지 않았다면 (현재 키높이 : 인원수 1) 형태로 스택에 추가하면 된다.

 

즉 스택이 top으로 갈수록 내림차순을 유지하면 서로 바라볼 수 있는 쌍을 알아낼 수 있다.

 

정답 코드