백준 3015 - 오아시스 재결합

🔐 백준 3015 - 오아시스 재결합

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

🔑 풀이

서로 볼 수 있는 사람의 쌍의 수를 세는 문제이다.

키가 같은 사람이 여러 번 나왔을 때 어떻게 처리할 것인지를 주의해야 한다.

스택에 키를 저장할 때, 키가 같은 사람의 수를 같이 저장하여 문제를 해결한다.

알고리즘

입력 받은 수를 h 라 하면,

1. 스택에 있는 사람들 중 h보다 작거나 같은 사람들은 h와 서로 볼 수 있다.

2. 스택에 있는 사람들 중 h보다 작은 사람은 h 이후의 어떤 사람도 볼 수 없다.

3. 스택에 h보다 작거나 같은 사람을 세고(pop) 남은 사람이 있다면, 그 사람은
   h보다 큰 사람이며, 그 사람과도 서로 볼 수 있다.

🧩코드