[알고리즘 문제] 이사 (Python / 파이썬)

문제

지니는 이사 준비에 바쁘다.
지니에게는 이사 짐을 담을 수 있는 박스 N개와 이사 짐 M개가 있다. 이사 짐을 담을 수 있는 박스는 담을 수 있는 무게가 정해져 있다. 안정상의 문제로 지니는 정해진 무게보다 무조건 무게가 작은 짐만 담을 것이다. 각 박스에 담을 수 있는 이사 짐의 개수의 합을 출력하는 프로그램을 작성하라.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N, M이 공백으로 구분되어 주어진다.
각 테스트케이스의 둘째 줄에 각 박스에 담을 수 있는 무게가 공백으로 구분되어 주어진다.
각 테스트케이스의 셋째 줄에 이사 짐의 무게가 공백으로 구분되어 주어진다.
박스의 무게 재한과 이사 짐의 무게는 모두 1,000,000 이하의 자연수다.
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 20,000, 1 ≤ M ≤ 20,000 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 각 박스에 담을 수 있는 이사 짐의 개수의 합을 출력한다.

---

문제 풀이

각 박스에는 담을 수 있는 무게보다 작은 짐만을 담을 수 있다. 

그래서 처음엔 2중 for 문을 이용해 문제를 해결하려 했으나

시간 초과 문제가 발생하였다. 

 

따라서 다른 방법으로 문제를 해결해보았다. 

먼저 박스에 담을 수 있는 무게와 이사 짐의 무게를 오름차순으로 정렬한다.

그런 다음 박스에 담을 수 있는 무게 보다 이사 짐의 무게가 같거나 클 때까지 

인덱스를 1씩 증가시켜준다. 

그럼 결국 현재 박스에 담을 수 있는 무게보다 더 작은 무게들의 개수를 세어주는 것이다. 

따라서 인덱스의 값을 구할 때마다 더해주면 이사 짐 개수의 총 합을 구할 수 있다. 

---

My Code

for tc in range(int(input())):
    n, m = map(int,input().split()) # 박스와 이사 짐의 개수

    box = list(map(int,input().split())) # 각 박스에 담을 수 있는 무게
    stuff = list(map(int,input().split())) # 이사 짐의 무게

    box.sort() # 오름차순으로 정렬
    stuff.sort() # 오름차순으로 정렬

    idx = 0 
    sum_value = 0
    for i in range(n):
        # 이사 짐의 무게가 더 크거나 같을 때까지
        while idx < m and box[i] > stuff[idx]:
            idx += 1 # idx를 더해줌 (더 작은 것의 개수를 세어줌)
        sum_value += idx # 더 작은 것들의 개수를 더해줌

    print('#' + str(tc + 1), end = ' ')
    print(sum_value)