[Kickstart][2020][Round F] 1. ATM Queue

문제 : codingcompetitions.withgoogle.com/kickstart/round/000000000019ff48/00000000003f4ed8

---

 

ATM기에 돈을 인출하기위해 사람들이 서있다.

사람들은 Ai 만큼의 돈을 인출하고 싶어한다. 한 번에 인출할 수 있는 돈의 최대는 X이다.

만약 한 번에 원하는 돈을 인출할 수 없다면 돈을 인출한 수 사람들이 서 있는 줄의 가장 뒤에 선다.

원하는 돈을 전부 인출했다면 줄에서 이탈한다.

사람들이 인출하고자 하는 비용 배열 A. 사람의 수 N, 최대 인출 가능 금액 X가 주어질 때, 줄에서 이탈하는 사람들의 순서를 구해라.

---

i 번째 사람이 인출하고자 하는 총 금액이 Ai라 할 때, 줄에 총 몇번 서는지 먼저 구한다.

줄에 서는 총 횟수는  (Ai + X - 1) / X  수식으로 O(1)만에 구할 수 있다.

X-1 / X 는 Ai % X 가 0보다 큰 경우 1을 더하는 수식과 동일하다.

줄에 서는 총 횟수를 오름차순 정렬한다. 만약 동일한 횟수가 있다면 처음 줄에 선 순서 기준으로 오름차순한다.

정렬된 배열을 앞에서부터 탐색하며 처음 줄에 선 순서를 출력한다.

 

시간복잡도는 정렬하는데 가장 시간이 많이드므로 O(NlogN).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundF/1.%20%20ATM%20Queue.cpp