programmers - 숫자게임

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

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

먼저 처음에 짠 코드

def solution(A, B):
    answer = 0
    A = sorted(A,reverse=True)
    B = sorted(B,reverse=True)
    for _ in range(len(B)):
        a = A.pop(0)
        b = B.pop(0)
        if a < b:
            answer += 1
        else:
            continue

    return answer

위와 같이 코드를 짜면 시간 복잡도가 N^2 이 나오게 된다. 따라서 시간초과가 뜬다.

pop(0)을 사용하면 안되고, pop() 을사용해서 하기위해서

def solution(A, B):
    answer = 0
    A.sort(reverse = True)
    B.sort(reverse = True)
    
    for _ in range(len(B)):
        if A[-1] >= B[-1]:
            B.pop()
        else:
            A.pop()
            B.pop()
            answer += 1
    return answer

위와 같은 코드로 작성했다. 

pop(0), remove, find, del, index 등의 함수가 나오면 자리를 옮기는데 o(N)이 들기 때문에 for문 하나만 안에 오더라도

시간초과가 뜰 가능성이 높아지기 때문에 index는 cursor 변수를 이용해서 하거나 remove나 del같은 건 스택 구조를 이욯해서 생각하도록 해야겠다.