(출처) https://algospot.com/judge/problem/read/NERD2
문제 자체는 간단하다
입력으로 들어오는 사람 N 명을, 나머지 N-1 명과 전부 비교한다. N-1 명 중에 자신보다 라면값과 문제값이 모두 큰 사람이 1명이라도 있다면 대상인원은 대회에 참여가 불가능하다. 따라서 N * (N - 1) 번 계산을 수행하여 대회에 참여가능한 인원만 추려내면 되는 간단한 문제이다.
문제에서는 매번 사람이 들어올 때마다 참여가 가능한 인원수를 따로 세준 뒤에 최종적으로 합한 값을 요구하고 있으므로 위의 로직을 다시 N 번 돌려주어야 한다. 결국 총 O(N^3)이면 답을 구할 수 있다.
(물론 계산을 진행하면서 ret 값을 따로 유지해 준다면 O(N^2)으로도 해결할 수 있기는 하다)
위의 로직대로라면 굉장히 쉽게 구현이 가능한 문제다. 하지만 아쉽게도 들어올 수 있는 N의 최댓값이 50,000 개이므로, 시간복잡도가 O(N^2)만 되더라도 절대로 문제에서 주어진 2초 안에 모든 계산을 해결할 수 없다.
최적화가 필요하다. 어떤 방식으로 최적화를 해야 할지 한번 고민해 보라고 대놓고 유도하고 있는 문제 같았다.
1명씩 들어올 때마다 nerd 멤버를 갱신해야한다
N 명의 사람이 입력으로 들어오므로 적어도 N 명은 한 번씩은 무조건 확인해 주어야 한다. 따라서 O(N)의 복잡도는 반드시 소요된다.
문제는 N 번의 탐색을 진행하면서 각 대상 인원이 nerd인지 판단하고, 대상 인원의 NERD 포함여부에 따라서 달라진 현재까지의 NERD 멤버를 확인하는데 O(N) 미만의 시간복잡도를 사용해야 한다는 것.
만약 이 과정에서 O(N) 이상의 시간복잡도를 소모한다면 전체 시간복잡도는 O(N^2) 이상이 되어버리므로 시간제한에 걸리고 만다.
따라서 한 번의 인원 검사마다 NERD 멤버 자료구조를 새롭게 갱신해야 하고, 그 갱신시간이 O(N) 미만이 되도록 설계해야 한다.
그러기 위해서는 검사를 받는 대상 인원을, 현재까지의 NERD 멤버 최대 N 명과 모두 한 번씩 비교해봐서는 안된다. NERD 멤버에 존재하는 N 명을 모두 확인해 본다면 결국은 O(N)의 시간복잡도가 소모될 것이기 때문이다.
존재하는 N 명을 모두 확인해 보지 않고, 대상 인원이 너드인지 판단하며 새롭게 NERD 멤버진을 갱신해 줄 수 있는 방법은 무엇이 있을까?
NERD를 라면or문제수 를 기준으로 정렬해보자
우선은 지금까지 NERD 로 판명된 인원들을 모아놓을 때 해당 인원들을 라면수 혹은 문제수를 기준으로 정렬한 채로 모아놓는다면 어떨까? 라는 생각을 해보았다.
만약 NERD 인원들만을 모아놓은 특정 자료구조를 라면수를 기준으로 정렬해놨다고 하자. 그리고 이제 검사 대상이 되는 인원을 NERD 모음에 집어넣는다고 생각해보면 삽입한 검사대상인원의 인덱스 앞에 오는 인원들은 더 적은 라면수를 가지게 될 것이고, 뒤에 오는 인원들은 더 많은 라면수를 가지고 있는 형태가 될 것이다.
그런데 이때 정렬된 NERD 인원들을 보면 한가지 재미있는 특성을 가지고 있는 것을 알 수 있다. 라면을 기준으로 오름 정렬을 하게되면 NERD 인원들의 문제수 또한 동시에 내림 정렬된 상태가 된다는 것이다.
물론 검사대상인원을 삽입하기 전, 기존의 NERD 인원에서 이미 내림 정렬을 벗어난 인원이 존재하고 있을 가능성은 없다. NERD 조건을 만족하는 인원만 모아서 보관한다는 최초의 정의에 의해서 모든 기존 NERD 인원은 내림정렬조건을 만족해야하기 때문이다.
따라서 이 특성을 이용하여 검사대상인원을 현재 NERD 목록에 넣을 수 있는지 없는지를 쉽게 판단할 수 있다. 판단과정은 검사대상인원의 바로 뒤에 있는 기존 NERD 인원의 문제수와 비교하여 내림정렬이 유지되는지 확인만 해주면 된다. 만약 검사대상인원의 위치만 파악할 수 있다면 O(1) 상수시간만으로 판단이 가능하다.
만약 내림정렬이 유지되지않아 검사대상인원이 NERD 인원에 포함될 수 없다면 NERD 목록은 변동이 생기지 않을테니 바로 다음 검사대상인물을 확인하면 된다. 하지만 검사대상인원이 NERD 인원에 적합한 인물로 판명이 난다면 다시 추가적인 검사가 필요하게 된다.
이때 삽입한 검사대상인원의 뒤에 있는 인물들은 물론 추가적인 검사를 할 필요가 없다. 해당 인물들은 검사대상인원보다 라면수가 크고 문제수 내림정렬이 유지되는 인원들만 존재한다는 것을 이미 확인했기 때문에 새로운 인원이 추가되어도 자연스럽게 NERD 조건을 유지한다.
하지만 그 앞에 있는 인물들은 새로운 인원이 추가됨으로 인해 문제수 내림정렬의 유지가 깨지게 될 가능성이 존재한다.
따라서 목록에 삽입한 검사대상인원의 바로 앞에 있는 인원부터 시작해서, 검사대상인원과 문제수 내림정렬이 유지되고 있는 지를 1명씩 비교하며 확인해주어야만 한다.
만약 내림정렬이 유지되지 않는 경우를 발견한다면, 내림정렬유지조건에 인해 기존의 NERD 인원은 더이상 NERD의 인원이 아니게된다. 따라서 해당 인원을 NERD 목록에서 삭제시켜 버리고 내림정렬을 유지시키는 인원을 발견할 때 까지 판단과정을 반복해준다.
만약 검사대상과 내림정렬을 유지시키는 인원을 발견했다면 이제 검사를 종료해도 된다. 해당 인원의 앞에있는 나머지 인원들은 NERD는 내림정렬이 유지되야 한다는 조건으로 인해 이미 내림정렬이 되어 있을 것이 때문이다.
시간복잡도
해당 문제는 결국 검사대상인원 N명을 검사하는 N번의 반복동안 진행하는 검사로직에 따라 시간복잡도가 결정된다.
먼저 정렬된 기존의 NERD에 검사인원대상이 삽입될 위치를 찾는 과정은 후에 생각하기로 하자.
검사대상인원의 삽입위치를 결정지었다면 NERD에 포함시킬 수 있는 지 없는 지에 대한 판단은 위에 설명했듯이 O(1) 상수 시간이면 된다.
하지만 만약 검사대상인원이 NERD에 포함된다면 삽입한 검사대상인원 바로 앞의 인원부터 시작해 하나씩 탐색을 진행하며 조건에 위반되는 인원을 삭제해주어야한다. 이때 조건에 위반되는 인원이 없다면 1번의 비교만으로도 탐색이 종료된다. 하지만 조건에 위반되는 인원이 존재한다면 계속해서 탐색은 진행된다.
결국 이 탐색의 진행은 삭제되는 인원이 존재할때만 유지된다. 그런데 삭제되는 인원은 아무리 많아봐야 전체인원 N명을 초과할 수 없다. 즉 총 검사대상인원 N명을 검사하는 N번의 반복동안 일어나는 인원의 삭제(=인원제거탐색진행횟수)를 모두 세봐야 최대 N번이다.
각 반복동안 N번의 탐색(=N번의 삭제)이 진행된다는 것이 아니라, N번의 반복을 모두 진행했을 때 삭제되는 인원의 최대가 총 N개라는 것이므로, 기존 NERD 인원삭제를 위한 탐색진행횟수도 결국 총 O(N)이 소모된다.
그럼 이제 계산에 남은 것은 정렬된 기존 NERD들에 검사대상인원의 삽입위치를 찾는 최초의 공정뿐이다.
사실 삽입위치를 찾는 것도 어렵지는 않다. 만약 기존에 원소들이 이미 정렬된 상태였다면 새로운 원소가 삽입될 위치를 찾는 것은 이분검색을 이용하면된다. 이것은 O(lg N)이면 해결 할 수 있다. 하지만 나는 삽입될 위치를 찾는 것뿐만 아니라 실제로 원소를 계속해서 삽입시켜 주어야 한다.
만약 배열을 이용하여 해당 삽입과정을 구현한다면, 위치를 찾고 새로운 원소를 삽입할때 마다 lg N + (N - 새로운 원소 삽입으로 인해 이동된 배열원소의 개수) 의 시간복잡도를 소요하게 된다. 굉장히 비효율적이다.
따라서 결국 해당 문제는 자료구조에 대한 고민으로 넘어간다. 정렬된 자료들에 정렬이라는 특성을 유지한채로 새로운 원소를 빠르게 삽입할 수 있는 자료구조를 이용해야 한다. 그리고 이러한 자료구조로는 이진검색트리가 있다.
결국 NERD를 이진검색트리인 map으로 구성하게된다면 정렬을 유지한채로 중간에 새로운 원소를 삽입하는 시간을 단 O(lg N)만에 해결 할 수 있게 된다.
따라서 전체 시간복잡도 O(N * lg N)으로 해당 문제를 해결할 수 있게 된다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
map<int, int> nerds;
int nerd2(int p, int q) {
auto iter = nerds.insert({ p, q }).first;
//map에 등록이 불가능한 경우, 대상 노드가 너드가 아닌 경우
int target_q = (*iter).second;
iter++;
if (iter != nerds.end()) {
int next_q = (*iter).second;
if (target_q < next_q) {
iter--;
nerds.erase(iter);
return nerds.size();
}
}
iter--;
//map에 등록이 가능한 경우, 대상 노드가 너드인 경우
while (true) {
if (iter == nerds.begin()) return nerds.size();
target_q = (*iter).second;
iter--;
if (target_q > (*iter).second) iter = nerds.erase(iter);
else return nerds.size();
}
}
int main() {
int testcase;
cin >> testcase;
while (testcase--) {
int n;
cin >> n;
int p, q;
scanf("%d %d", &p, &q);
nerds.clear();
nerds.insert({ p, q });
int ret = 1;
for (int i = 0; i < n - 1; i++) {
scanf("%d %d", &p, &q);
ret += nerd2(p, q);
}
cout << ret << "\n";
}
}
기억하고 싶은 점
이진검색트리 그 중에서 균형잡힌 블랙레드트리인 map의 장점을 잘 느낄 수 있게 해준 문제였다.
그리고 특히 책의 해답에서 라면수와 문제수를 x,y 좌표위에 올려 2차원적으로 생각하는 발상이 굉장히 놀라웠다.
내가 문제를 풀었던 논리와 결국 똑같은 논리이긴하지만 확실히 이렇게 눈에 보이기 쉽게 생각을 이어가니 더 직관적이고 이해하기 쉬웠다.
