[KickStart] Round F 2020 - ATM Queue

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

Kick Start - Google’s Coding Competitions

 

Problem

There areNpeople numbered from 1 toN, standing in a queue to withdraw money from an ATM. The queue is formed in ascending order of their number. The person numberediwants to withdraw amountAi. The maximum amount a person can withdraw at a time isX. If they need more money thanX, they need to go stand at the end of the queue and wait for their turn in line. A person leaves the queue once they have withdrawn the required amount.

You need to find the order in which all the people leave the queue.

Input

The first line of the input gives the number of test casesT.Ttest cases follow.

The first line of each test case gives two space separated integers: the number of people standing in the queue,Nand the maximum amountXthat can be withdrawn in one turn.The next line containsNspace separated integersAi.

Output

For each test case, output one line containingCase #x: y, wherexis the test case number (starting from 1) andyis the space separated list of integers that denote the order in which the people leave the queue.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤T≤ 100.

Test Set 1

1 ≤N≤ 100.
1 ≤$A_i$≤ 100.
1 ≤X≤ 100.

Test Set 2

1 ≤N≤ $10^5$for at most 10 test cases. For the remaining cases, 1 ≤N≤ 100
1 ≤$A_i$≤ $10^9$.
1 ≤X≤ $10^9$.

---

풀이 방법

이 문제를 처음에는 큐를 사용해서 접근해야하나 고민을 했습니다.

그러나 테스트 케이스에서 보면 $10^9$ 까지 가기 때문에 일반적인 $O(n\log n)$의 방식으로 풀면 안되겠다는 생각을 했습니다. 이분탐색을 하는 문제는 index때문에 아니었구요.

그래서 생각해낸 방법은 입력을 받은 것에 X값을 나눠주고 그것을 sort하면 되는 간단한 문제였습니다. 아래는 그 코드입니다.

def solution():
    res = []
    N, X = list(map(int, input().split()))
    A = list(map(int, input().split()))

    Aj = [[i+1, (A[i]-1)//X] for i in range(len(A))]
    #print(Aj)

    Aj.sort(key=lambda x : x[1])

    answer = " ".join([str(a[0]) for a in Aj])
    return answer

N = int(input())
for i in range(N):
    result = solution()
    print("Case #{}: {}".format(i+1, result))