문제

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

나의 코드 (답안 참조)

"""
1. 아이디어
이 문제의 핵심은 제한사항을 잘 읽어보아야 한다고 한다.
제한 사항을 잘 파악했느냐에 따라 이 문제를 풀 수 있냐 없냐를 따질 수 있다고 한다.
"중복이 없다", "여별이 있는 학생도 도난 당할 수 있다"라는 문구를 참조해서 lost와 reserve에
같은 숫자가 있다면 제외시켜 주어야 한다는 것을 알 수 있다.

2. 시간복잡도
반복문 내에서는 비교 연산자와 set자료형에서 remove 밖에 없기 때문에 O(n)이다.
( set자료형 remove 시간복잡도 O(1) )
"""

def solution(n, lost, reserve):
    
    """ 제한사항에서 중복은 없다고 하였기 때문에 set()자체는 아무런 의미가 없다.
    하지만 여벌이 있는 학생도 도난 당할 수 있다는 조건 때문에 lost와 reserve에
    같은 값이 있다면 set()자료형의 -연산자 즉, 차집합을 통해 제외 시켜준다."""
    set_lost = set(lost) - set(reserve)
    set_reserve = set(reserve) - set(lost)
	
    """ lost = [2, 4], reserve = [3, 5]의 경우 3번 학생은 2번 학생을 먼저 확인 후 
    4번학생에게 빌려 주어야 한다. 만약 3번 학생이 4번 학생부터 확인한다면 5번 학생의 경우 
    빌려 줄 곳이 없기 때문에 문제의 조건인 최대한 많은 학생이 수업에 참여할 수 없게 된다.
    그렇기 때문에 앞에 사람부터 탐색 후 뒤에 사람을 탐색해야 한다. """
    for i in set_reserve:
        
        if i-1 in set_lost:
            set_lost.remove(i-1)
        elif i+1 in set_lost:
            set_lost.remove(i+1)
                
    return n - len(set_lost)

느낀점

그리디(Greedy) 문제가 쉬우면 쉽지만 어렵게 내면 어려울 수 있는 문제이다.
이 문제는 쉬운 편에 속하지만 제한사항을 제대로 읽지 않는다면 삽질할 수 있는 문제 이기 때문에 문제를 꼼꼼하게 읽을 필요가 있다.

참고자료

[체육복 문제에 대해 자세히 설명해주고 있다.]
https://rain-bow.tistory.com/30