[알고스팟] NERD2 - 너드인가, 너드가 아닌가? 2 (C++, 이진 검색 트리)

문제

 

https://algospot.com/judge/problem/read/NERD2

algospot.com :: NERD2

 

 

풀이

 

종만북 난이도: 중

 

STL의 map 자료구조를 이용하면 직접 이진 검색 트리를 구현하지 않아도 풀 수 있다.

map은 key와 value 쌍을 pair<,>자료구조로 저장한다.

이때 value들은 key값을 기준으로 이진 검색 트리에 정렬되어 저장된다.

 

너드 지수를 구하는 값 p와 q를 아래와 같이 2차원으로 나타내 보자.

참가자 4명의 너드 지수가

 (p,q)

1.50,30

2.20,40

3.30,20

4.40,35

순서대로 주어진다고 하자.

 

참가자 1번은 2번보다 p값이 크고 2번은 q값이 더 크므로 둘 다 참가 자격이 있다.

이후 3번이 참가신청을 했다면 1번보다 큰 값이 없기 때문에 참가할 수 없다.

즉, 2차원으로 나타냈을 때 1번이 이루는 직사각형 범위 안에 들어가기에 참가하지 못한다.

4번 참가자는 1번보다 p값은 작지만 q값이 크고, 2번보다 p값은 크지만 q값은 작다.

따라서 4번은 참가 자격이 있다.

 

이때 4번이 2차원에서 이루는 사각형까지 생각해보자.

참가 자격이 있기 위해서는 이미 참가자격이 있는 사람들보다 p와 q중에 적어도 한 값은 커야 한다.

즉  다른 사람의 값이 이루는 직사각형의 범위 내에 들어가서는 안된다.

또한 이런 직사각형들은 오른쪽으로 갈수록 p값은 커지고 q값은 작아지는 계단 형태를 이룬다.

 

따라서 새로운 참가자의 자격을 확인하기 위해서는 자신의 p값의 앞에 존재하는 참가자의 q값을 비교하면 된다.

자신보다 p값이 큰 참가자 중에서 가장 p값이 작은 참가자(바로 앞의 참가자, k라고 하자)보다는 q값이 크다면 참가 자격이 있다. 

그 이유는 k보다 p값이 더 큰 참가자들은 k보다는 q값이 작기 때문에 k가 참가자격을 얻을 수 있었기 때문이다.

새로운 참가자는 k보다 q값이 크다면 자신보다 p값이 큰 참가자들보다는 q값이 크고

자신보다 p값이 작은 참가자들보단 p값이 더 크기에 참가자격이 있다.

 

자신보다 p값이 큰 참가자 중에서 가장 p값이 작은 참가자를 찾기 위해서는 map 자료구조의 

lower_bound(p)를 사용하면 간편하게 구할 수 있다.

lower_bound(p)는 key값이 p보다 크거나 같은 값 중에서 가장 작은 값의 iterator를 반환해준다.

 

 

 

만약 새로운 참가자(newbie)보다 p값이 작은 참가자들 중에newbie보다 q값이 작은 이가 있다면 자신보다 p, q값이 모두 큰 참가자가 있기 때문에 참가자격을 박탈해야 한다.

lower_bound(p)를 이용하여 자신에서 부터 시작해 첫 값까지 자신보다 q값이 작은 참가자를 찾아내 map에서 erase 해주자.

이때 iterator를  lower_bound(p)에서 부터 begin()까지 진행하는 이유는 map의 begin에서부터 q값이 작은 것을 찾아낸다면  lower_bound(p)까지 모두 찾아보아야 한다. 이러한 작업은 q값이 더 작은 참가자가 없더라도 처음부터 끝까지 트리를 서칭 해야 하므로 O(n^n)의 작업이 필요하다.

하지만 그 역순으로 진행한다면 참가자들의 q값은  begin()으로 진행해 갈수록 점점 커진다. 따라서 newbie보다

q가 큰 참가자가 발견되면 그 이후의 값들은 더 이상 찾아보지 않아도 newbie보다는 q값이 크다.

또한 q값이 작은 참가자들은 erase 되어 더 이상 트리상에 존재하지 않으므로 모든 노드들은 결국 한 번씩만 방문된다.

따라서 O(n)의 복잡도를 갖는다.

 

추가적으로 주의할 점은 

iterator를 사용하여 --iterator로 앞의 값으로  반복자를 이동시킬 때 해당 값을 이미 map에서 erase 해주었다면 지워진 반복자를 이동시켜 오류가 발생한다.

따라서 미리 값을 복사하여 이동시켜준 후 그 값을 이용하자.

 

 

 

코드