[프로그래머스/Python] Level 3_최고의 집합(연습문제)

📌문제 유형

연습문제

 

📌문제

프로그래머스

 

📌나의 문제풀이

- 시간초과 , 10만이기 때문에 비효율적

from itertools import permutations

def solution(A, B):
    answer = -1
    combi = list(permutations(B,len(B)))
    
    for c in combi:
        ans = 0
        for i in range(len(c)):
            if A[i] < c[i]:
                ans += 1

        if ans > answer:
            answer = ans
            
    return answer

 

- A 내림차순, B rotate 하면서 비교

• 정확성 만점, 효율성 0

from collections import deque
import copy

def solution(A, B):
    answer = 0
    
    A.sort(reverse = True)
    B.sort(reverse = True)
    C = copy.deepcopy(B)
    
    B = deque(B)
    
    while True:
        result = 0
        for i in range(len(A)):
            if A[i] < B[i]:
                result += 1
        if result > answer:
            answer = result
        B.rotate(1)
        
        if list(B) == C:
            break
            
    return answer

 

- 정답

• B배열 내 제일 작은 원소, A 못이김 -> B삭제

from collections import deque
import copy

def solution(A, B):
    answer = 0
    
    A.sort()
    B.sort()
    
    A = deque(A)
    B = deque(B)
    
    while B:
        if A[0] < B[0]:
            A.popleft()
            B.popleft()
            answer += 1
        else:
            B.popleft()
            
    return answer

 

📌리뷰

- 10만이기에 그냥 비교하면 못함 -> deque 생각하기

- 핵심 : B 배열의 가장 작은 원소, A 못이김 - A,B 오름차순 정렬 후 B가 작으면 B만 빼기