[정렬 및 탐색] 백준 7795 (파이썬)

 

 

이전에 풀 때는 PyPy3이라서 속도가 빨라서 그런지 성공했었는데

Python3로 언어를 설정해서 돌리면 '시관초과'가 난다.

 

이전의 풀이는 아래와 같은데 시간초과가 날 것을 생각해서

1) aArray와 bArray를 순차탐색 하기 전에 sort함수로 올림차순해주고

2) aArray의 요소가 bArray의 요소보다 크다면 바로 break로 2중 for문을 탈출하면

시간초과가 나지 않을 거라고 생각했다.

import sys

testCase = int(input())

aArray = []
bArray = []
for _ in range(testCase):
    cnt = 0
    aLen, bLen = map(int, input().split())
    aArray = list(map(int, sys.stdin.readline().strip().split()))
    bArray = list(map(int, sys.stdin.readline().strip().split()))

    aArray.sort()
    bArray.sort()
    for a in range(aLen):
        for b in range(bLen - 1, -1, -1):
            if aArray[a] > bArray[b]:
                cnt += (b + 1)
                break

    print(cnt)

 

 

 

하지만 이건 역시 최악의 경우 O(N^2)이기 때문에 새로운 방법이 필요하다.

 

 

순차탐색보다 시간복잡도가 덜 걸리는 이중탐색을 사용해야 한다는 것이다.

이중탐색은 시간복잡도가 O(logN)이 걸리기 때문에 전체적으로 N*O(logN)이 걸릴 것이라 괜찮을 것 같다.

 

하지만 이중탐색은 특정 요소를 찾는 과정만 해봤는데

특정 요소보다 작은 요소들의 갯수를 찾기 위해 자신의 위치를 찾는? 작업은 해보지 않아서 막막했다.

 

https://jinho-study.tistory.com/311

백준 알고리즘 7795번 먹을 것인가 먹힐 것인가(python)

 

 

위의 블로그를 보고 bisect를 import 해서 푸는 방법, 이중탐색처럼 따로 함수를 만들어 호출하는 방법이 있는 것을 알았다.

 

bisect는 이중탐색을 위한 라이브러리이고, 

bisect_left(array,4)를 예를 들어 한다면 왼쪽부터 4가 들어갈 위치를 찾는 것이다.

따라서 특정 숫자의 위치를 찾게 되면 그 보다 작은 왼쪽 요소들의 갯수를 알 수 있고, 더 작은 시간복잡도로 해결 할 수 있다.

bisect라이브러리를 사용해서 해결

 

이중탐색을 사용해서 해결