1946 신입 사원

n명의 사람의 a,b의 순위가 주어질 때, 어떤 사람에게도 a,b 모든 순위에서 지면 제외시킨다고 할 때, 살아남는 사람의 숫자를 구하는 문제이다.

생각보다 고민한 문제인데,  내가 푼 방법은 우선 a순위를 정렬하는것이다.
한 순위를 정렬하게 되면(순위가 높은 순으로), 다음 과 같이 구분한다.

1. 1순위는 무조건 추가한다. 1순위는 무조건 살아남기 때문이다.
2. 그 다음 2순위부터 차례대로, 이미 추가된 사람들의 b순위와 비교한다.
2순위는 1순위보다 무조건 a에서 지지만, b에서 이기면 살아남는다.
따라서 이미 추가된 사람들의 b순위보다 순위상 위라면 추가해준다.

위와 같은 방법으로 문제 해결이 가능하지만, 사실 그대로 구현하면 TLE가 나오게 된다.
시간복잡도가 정렬하는대서 O(nlog(n)), 아래 비교하는대서 O(n^2)이 뜨기 때문이다.

TLE를 해결하려면 2번을 고쳐줄 필요가 있다.
2번에 이미 추가된 사람들의 b순위를 하나하나 비교하지 말고, 추가된 사람 중에서 가장 높은 b순위를 max로 저장하고 이것하고만 비교해주면서 갱신하면 된다.
여기서 max만 갱신해주면 딱히 추가할 필요도 없어져서 메모리 절약도 가능하다.
이 때의 시간복잡도는 O(n)이 된다.

소스