프로그래머스 - 숫자 게임 (Summer/Winter Coding) / Level 3

문제 📋

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

풀이 📝

def solution(A, B):
    answer = 0
    n = len(A)
    start = 0
    
    A.sort()
    B.sort()
    
    for i in range(n):
        for j in range(start, n):
            if B[j] > A[i]:
                answer += 1
                start = j+1
                break
    return answer

레벨 3치고 쉬운 문제였다.
기본적으로 입력의 크기를 보고 모든 경우의 수를 다 체크해서 최대값을 구하겠다는 생각은 버려야 한다.
또한 대소를 비교하는 문제이기 때문에 두 리스트를 정렬하고자 하는 생각이 중요했다.

정렬 이후에는 A팀 하나의 점수보다 큰 값을 B팀 리스트에서 찾게 되면
그 이전 값들을 볼 필요가 없어지기 때문에 A리스트를 한번 순회할 동안
B리스트도 한번만 순회하면 된다.
따라서 시간복잡도를 2n 정도로 줄일 수 있다.