https://www.acmicpc.net/problem/1946
1946번: 신입 사원
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
www.acmicpc.net
1. 첫 번째는 입력은 순위 입니다(점수가 아님) --조심 !
2. 전 첫번째 제출한 코드는 시간초과가 되었습니다. 당연한 것이 최악의경우를 생각해보면
입력을 고려해 보았을 떄 10000000000 이는 약 1억번 연산이 1초라고 계산해보면
당연히 시간초과가 나올 수 밖에 없겠죠.
3. 그래서 우선 서류점수로 오름차순 정렬을 한후
반복문을 돌리는데 이때는 전체를 다 탐색할 필요가 없이 본인보다 서류점수 우선순위가 높은 사람들
(즉 본인보다 낮은 index)
의 면접점수만 확인 하면 되기 때문에 입력이 커질경우 연산 횟수를 대폭 줄일 수 있습니다.
** 그리고 저 같은 경우 vector를 사용하였는데 시간적 측면에서 더 단축 하고 싶다면
그냥 max값을 define 하여 그만큼의 배열을 잡아 버리는 것이 시간적 측면에서는 더 이득인 것 같더라구요 !
<시간초과 코드>
<맞춘 코드>
