[BOJ] 3015 오아시스 재결합

3015번: 오아시스 재결합

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

7
2
4
1
2
2
5
1

출력

서로 볼 수 있는 쌍의 수를 출력한다.

 

10

---

 

오랜만에 복잡한 알고리즘 문제가 아닌 자료구조를 잘 사용하는 문제를 풀었다.

그냥 Brute-Force 하게 풀 수도 있는 문제지만 시간 복잡도가 문제가 된다.

따라서 O(N) 안에 문제를 해결해야 한다.

 

스택을 내림차순으로 유지하면서 원소를 push 한다.

이때 키가 같은 경우가 있을 수도 있다.

이런 경우엔 스택을 압축하기 위해 중복 횟수를 따로 저장하고

중복되는 원소는 하나만 스택에 집어넣는다.

따라서 스택을 pair로 만들어서 사용했다.

 

사실 이 문제도 혼자서 하다가 결국 다른 블로그를 참고해서 풀었다.

그런데 거의 다 근접한 상태에서 조금의 디테일이 부족한 상태였다.

자료구조는 거의 바꾼 게 없고 for문 마지막에 스택이 빈 경우만 처리해주니 맞을 수 있었다. 

 

스택이 비어있다면 이전에 들어온 원소들 중 현재 들어온 원소보다 더 큰 원소가 없는 상태다.

이 예외만 처리해줬다면 금방 풀었을 텐데 아쉬움이 남는다.

 

 

후기)

똑같은 자료 구조라도 어떻게 사용하느냐에 따라서 천차만별이다.

자료구조를 더 잘 다룰 수 있게 되면 좋겠다.

그리고 C++을 쓰면 쓸 수 록 C는 너무 불편한 언어인 것 같다.

C++은 신이야!