[프로그래머스 Lv3] - 숫자 게임 (Python)

---

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    for a in A :
        for b in B :
            if a < b :
                answer += 1
                B.remove(b)
                break
            if B.index(b) == (len(B) -1) :
                minV = min(B)
                B.remove(minV)
    return answer

 

 

나는 A, B 모두 오름차순해서 작은 숫자부터 비교할거라서 이중 for 문 돌렸다

 

1) B 배열을 순회하면서 A 보다 커지는 B 가 나온다면 그대로 배치하고 break

 

2) 만약 끝까지 돌았는데도 A 보다 큰 수가 없다면 남아있는 B 원소 중 가장 작은 수 배치

- 어차피 A 보다 큰 수가 없다면 버리는 숫자로 젤 작은 숫자를 배치한다는 의미..!!!

 

 

 

 

 

정확성은 다 통과했는데 시간 초과로 효율성에서 팽 당함 ㅎㅎ

 

그래서 생각했던 게 어차피 못 이기는 자연수 a 가 있다면

이중 for 문 들어가기 전에 제일 작은 b 로 배치하고 들어가면 좀 낫지 않을까 ,,, 하다가

 

 

 

 

 

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    
    while (len(A) > 0) :
        if A[-1] >= B[-1] :
            A.remove(A[-1])
            B.remove(B[0])
        else :
            A.remove(A[-1])
            B.remove(B[-1])
            answer += 1
    return answer

 

 

이렇게도 해봤는데 

정확성은 다 맞고 효율성은 3개 다 실패함 ㅠㅠ

 

왜 시간이 더 걸리는 거지 했는데

remove 연산 시간 복잡도가 O(n) 이었다,,,,,

 

 

 

 

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    a_i, b_i = -1, -1
    
    while (len(A) > 0) :
        if abs(a_i) == len(A) + 1 :
            return answer
        if A[a_i] >= B[b_i] :
            a_i -= 1
            B.remove(B[0])
        else :
            a_i -= 1
            b_i -= 1
            answer += 1

 

그래서 remove 로 삭제하는 대신 

A 원소 가리키는 a_i 와 B 원소 가리키는 b_i 선언해서 대신 해줬다

 

그리고 B 의 가장 작은 수로 배치해줄 때 굳이 min() 이용하는 대신

이미 오름차순되어 있으니까 B[0] 으로 바꿔줌 !!

 

마지막으로 A 원소가 다 없어져서

a 인덱스가 범위 벗어나면 바로 리턴해주고 끝 !!!! 드ㅜ뎌!!!