Python) 체육복

난이도 : Level 1
유형 : 탐욕법 (Greedy)
카테고리 : 프로그래머스
날짜 : 2022-02-07

문제 풀이

제한사항 중 중복이 없다, 여벌의 체육복이 있는 학생도 도난 당할 수 있다 라는 점을 유의해서 풀었다.

여기서 중복이 없다.는

reserve = [`1`,`1`,2] 일 때, 배열 내 1 중복 불가  
lost = [`2`,3,1,`2`] 일 때, 배열 내 2 중복 불가  

를 말한다.

여벌의 체육복이 있는 학생도 도난 당할 수 있다.는 lost 값에 reserve값이 공통적으로 존재할 수 있음을 말한다.

reserve = [`2`,3,4]와 lost = [1,`2`,3] 일 때, 배열 내 2가 공통적으로 존재할 수 있음

이 때 여벌의 체육복은 1개밖에 없다고 가정하기 때문에 reserve와 lost에 같은 값이 있다면 그 값은 reserve에서 제외시켜줘야 한다.

1. reserve의 요소들 중 lost에 동일하게 존재하는 값을 set을 사용하여 모두 제거한다.

   _reserve = set(reserve) - set(lost)
   _lost = set(lost) - set(reserve)

2. 체육복을 양 옆으로 나눠줄 수 있도록 하기 위해 왼쪽부터 탐색한다.

   for i in _reserve :
       if i-1 in _lost : # 왼쪽부터
           _lost.remove(i-1) 
       elif i+1 in _lost : # 오른쪽
           _lost.remove(i+1)

3. 총 학생 수(n)에서 체육복을 잃어버린 학생 수(lost)를 빼준다면 체육 수업을 들을 수 있는 학생의 수를 알 수 있다.

   for i in _reserve :
       return n-len(_lost)

전체 코드

def solution(n, lost, reserve):
# n : 전체 학생의 수
# lost : 체육복을 도난당한 학생들의 번호가 담긴 배열
# reverse : 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열

    _reserve = set(reserve) - set(lost)
    _lost = set(lost) - set(reserve)
    
    for i in _reserve :
        if i-1 in _lost :
            _lost.remove(i-1)
        elif i+1 in _lost :
            _lost.remove(i+1)
    
    return n-len(_lost)

다른 사람의 풀이

제한사항을 set이 아닌 not in 컴프리헨션으로 처리하였다.
for문 돌면서 foward, back을 확인하고, remove를 해주었다.

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]

    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)

    return n - len(_lost)