[프로그래머스] 탐욕법(greedy) - 체육복

문제링크

 

나의 풀이

1. 우선 여분을 갖고 있는 학생이 만약 도난을 당했을 때는 아무한테도 빌려줄수가 없기에 lost와 reserve에 같은 숫자가 있으면 제거 해주는 과정부터 거쳤다.
   집합은 차집합을 이용해서 원하는 원소를 뺄 수 있기에 간단하게 set (집합)을 이용했다.
2. for 반복문을 이용해서 잃어버린 학생 (lost)을 한명씩 뽑아 보았고, 해당 학생이 reserve에서 빌릴 수있는지 판단했다. 만약 reserve에서 lost에게 빌려줄 수 있다면, lost 리스트에서 삭제해버리는 과정을 거쳤다.
3. 만약 reserve에서 빌려줄 수없다면, 그 학생은 수업을 못듣는 것이기에 '전체학생수'에서 -1 해줬다. (어차피 수업듣는 학생은 처음에 n으로 시작한다.)

def solution(n, lost, reserve):
    
    n_lost = set(lost) - set(reserve)
    n_reserve = set(reserve) - set(lost)
    
    for i in n_lost:
        if i-1 in n_reserve:
            n_reserve.remove(i-1)
        elif i+1 in n_reserve:
            n_reserve.remove(i+1)
        else: # 도난당한 i에게 여분의 옷을 빌려줄 reserve가 없다면 전체 학생수 -1
            n -= 1
            
    return n

 

다른사람풀이

대부분 lost 와 reserve의 차를 이용해서 풀었고, 리스트에서 삭제하는 방식을 사용한 것같다. 많은 사람들이 비슷한 맥락으로 문제를 풀었다. 나는 "set"으로 이용해서 차집합을 이용한다는 것을 생각을 못했기에, 구글링으로 이부분만 찾아서 문제를 풀었다.
처음에는 for loop를 돌려서 reserve나 lost 안에서 해당 숫자의 존재 여부를 파악한 후, 새로운 n_lost, n_reserve로 append해주는 과정을 사용했는데, 반복문이 두개나 생겨서 시간복잡도 효율이 매우 낮았을 것이다. 차집합을 이용함으로써 간단하게 처리 할 수 있다는 것을 배웠다.