[코딩테스트 python] 프로그래머스 탐욕법(Greedy)

 

그리디(Greedy)

- 단순하지만 강력한, 현재 당장 좋은 것만 선택하는 알고리즘
- 대부분의 문제는 그리디 알고리즘을 적용했을 때 '최적의 해'를 찾을 수 없을 가능성 높음 > 정당한지 검토 필수!

 

프로그래머스

▲ 문제

 

def solution(n, lost, reserve):
    student=[1 for _ in range(n)] #전체 학생수 만큼 list 생성
    
    for lost_num in lost: 
        if lost_num in reserve:	#도난당했지만 여벌이 있는 학생 제외
            reserve.remove(lost_num)
        else:					#도난 당한 학생은 0으로 값 변경
            student[lost_num-1] = 0
    
    #앞의 학생부터 도난 당했는지 확인
    #reserve가 정렬이 안 되어 있으면 예외상황이 생김
    for r_num in sorted(reserve): 
        if r_num != 1 and student[r_num-2]==0:   
            student[r_num-2] = 1
        elif r_num != n and student[r_num] == 0:
            student[r_num] = 1
        else:
            pass

    return sum(student)

직관적으로 알기 쉽게 학생 수만큼의 배열 생성
> 정렬이 되어 있으면 앞 순서부터 도난 여부 체크만 하면 ok

but, 이렇게 풀면 학생 수가 많을 경우 비효율적.

 

다른 사람의 풀이를 보면
전체 학생 수 - 도난학생 수로 깔끔하게 풀이👍

 

기존에 푼 코드에 응용하면 ?

def solution(n, lost, reserve):
	# 여벌의 체육복을 가져온 학생이 1벌을 도난 당한 경우 제외
    _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 sorted(_reserve): 
        f = r - 1
        b = r + 1
        if r != 1 and f in _lost: #만약 1번학생이라면 앞번호가 없으니 제외
            _lost.remove(f)
        elif r != n and b in _lost: #만약 마지막 학생이라면 뒷번호가 없으니 제외
            _lost.remove(b)
        else:
            pass

    return n - len(_lost)

별도의 학생 리스트를 생성하지 않고
lost과 reserve를 비교해서 확인해서
빌려주면 lost에서 제거하는 식으로 학생 수 체크.

훨씬 간편!