[알고리즘] 프로그래머스 체육복 / python

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

코딩테스트 연습 - 체육복 | 프로그래머스

 

def solution(n, lost, reserve):
    answer = 0
    
    arr = [1] * (n + 2)
    
    for i in lost:
        arr[i] -= 1
    
    for j in reserve:
        arr[j] += 1
        
    for k in range(1, n + 1):
        if arr[k] == 2 and arr[k-1] == 0:
            arr[k-1 : k+1] = [1, 1]
        elif arr[k] == 2 and arr[k+1] == 0:
            arr[k : k+2] = [1, 1]
    
    answer = len([i for i in arr[1:-1] if i != 0])
    
    return answer

 

위 코드의 학생수 n은 많아야 30이다

만약, 학생수가 10000000이고 여벌의 체육복을 가져온 학생이 매우 적다면?

    -> 정렬하고, 순서대로 살펴보면서 처리한다. set 이용!

def solution(n, lost, reserve):
    answer = 0
    
    s = set(lost) & set(reserve)
    l = set(lost) - s
    r = set(reserve) - s
    
    for i in sorted(r):
        if i - 1 in l:
            l.remove(i - 1)
        elif i + 1 in l:
            l.remove(i + 1)
            
    answer = n - len(l)
    
    return answer

ser의 합집합 & , 교집합 | , 차집합 - ,