[백준] 7795 Python 풀이

https://www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

 

시간제한이 1초이다 브루트 포스로 순회해서 단순하게 풀면 시간초과가 난다 (!)
최근에 문제를 풀면서 깨달은 것인데, 선형 자료구조 (ex. list) 에서 시간 복잡도를 줄이기 위해서 유리하게 사용해볼 방법 중 하나가 바로 투포인터 알고리즘이다 

장점이라하면 포인터로 찍으면서 조건에 맞지 않은 후보들을 제쳐버려서 선형 자료구조를 보다 빨리 순회할 수 있다 ! 
그리고 투포인터를 유리하게 사용하기 위해서는 정렬이 필수이다. 파이썬에서의 정렬 알고리즘은 nlogn이니까 쓰기로 한다 

우선 첫번째 for 문에서 array_a[i] 를 하나씩 순회하면서 array_a에 있는 원소와 현재 포인터가 array_b에서 가리키고 있는 값을 비교한다. 그런데 우리는 이미 두 개의 리스트를 모두 오름차순으로 정렬해두었다

array_b[j]에서 array_a[i] 보다 같거나 큰 값이 나오면, 뒤에 남아 있는 array_b 의 원소들을 굳이 확인해 보지 않아도 이미 array_a[i] 보다 큰 값이기 때문에 break 문으로 불필요한 연산을 생략할 수 있다. 

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    array_a = list(map(int, input().split()))
    array_b = list(map(int, input().split()))
    # a가 b보다 큰 쌍의 개수
    array_a.sort()
    array_b.sort()
    count = 0
    j = 0
    for i in range(n):
        while True:
            if j == m or array_a[i] <= array_b[j]:
                count += j
                break
            else:
                j += 1
    print(count)