[Level 3] 숫자 게임

https://programmers.co.kr/learn/courses/30/lessons/12987

코딩테스트 연습 - 숫자 게임

---

접근

A와 B를 모두 오름차순으로 정렬한다. 그리고 A를 탐색하면서 해당 숫자보다 큰 것을 B에서 찾는다.

이때 idx를 사용하여 B를 탐색할 때 사용한다. 만약 A의 첫 번째 숫자보다 큰 것을 찾았다면 B를 처음부터 탐색하는 것이 아니라 큰 것을 찾은 다음 숫자부터 탐색하여 시간을 줄인다.

 

구현

- A와 B를 오름차순으로 정렬한다.

- A의 숫자를 처음부터 탐색한다.

- B에서 idx가 가리키는 숫자가 a보다 크면 idx를 증가시키고 종료한다.

- 아니라면 idx를 계속 증가시킨다.

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    N = len(B)
    idx = 0
    for a in A:
        while idx < N:
            if a < B[idx]:
                answer += 1
                idx += 1
                break
            idx += 1
    return answer