[프로그래머스/Programmers] 체육복 (풀이 언어 - Python/파이썬)

2023 Mar 15 in Computer Science on Algorithms & Data Structures

문제 설명

링크

• 잃어버린 아이템(체육복)을 기준으로 for-loop 체크를 한다.
• 전체 학생 수 \(n\)이 구간 [2, 30]에 속하는 정수값이고 알고리즘의 시간 복잡도는 \(O(n^2)\)이기 때문에 크게 최적화가 필요하지 않을 것 같아 보인다.
• lost와 reserve 사이에 중복을 제거하여 net_lost와 net_reserve를 set() 함수를 사용하여 만들어 주었다.
• 키워드 in의 시간 복잡도는 list에 대해선 평균 \(O(n)\)이나, set에 대해선 평균 \(O(1)\), 최악의 경우 \(O(n)\)이라는 점을 고려해 set을 사용했다.

풀이

def solution(n, lost, reserve):
    """
    Args:
        n: 전체 학생의 수
        lost: 체육복을 도난당한 학생들의 번호가 담긴 배열
        reserve: 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열
        
    Return:
        answer: 체육수업을 들을 수 있는 학생의 최댓값
    """
    
    net_lost = set(lost) - set(reserve)
    net_reserve = set(reserve) - set(lost)
    for lost_item in net_lost:
        if lost_item - 1 in net_reserve:
            net_reserve.remove(lost_item - 1)
        elif lost_item + 1 in net_reserve:
            net_reserve.remove(lost_item + 1)
        else:
            answer -= 1
    return answer

다른 풀이

참고

• 여분의 아이템을 기준으로 for-loop 탐색을 진행하는 방법

def solution(n, lost, reserve):
    """
    Args:
        n: 전체 학생의 수
        lost: 체육복을 도난당한 학생들의 번호가 담긴 배열
        reserve: 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열
        
    Return:
        answer: 체육수업을 들을 수 있는 학생의 최댓값
    """
    
    net_lost = set(lost) - set(reserve)
    net_reserve = set(reserve) - set(lost)
    for reserved_item in net_reserve:
        if reserved_item - 1 in net_lost:
            net_lost.remove(reserved_item - 1)
        elif reserved_item + 1 in net_lost:
            net_lost.remove(reserved_item + 1)
    answer = n - len(net_lost)
    return answer

참고

[1] Complexity of in operator in Python
[2] [Python] 프로그래머스 - 체육복