Step 2: 탐욕법(Greedy) 대표 문제 풀이: 체육복

강의

"탐욕법"은 알고리즘의 각 단계에서 그 순간에 지엽적으로 최적이라고 생각되는 것을 선택하는 알고리즘 입니다.

 

 

Step 2-3: 풀어서 내 것으로 만들자! 체육복

⭐ 직관적 풀이

def solution(n, lost, reserve):
    stack = [0] * n
    
    for student in range(1, n+1):
        if student in lost:
            if student in reserve:
                stack[student-1] = 1
                reserve.remove(student)
            else:
                if student-1 in reserve and student-1 not in lost:
                    stack[student-1] = 1
                    reserve.remove(student-1)
                elif student+1 in reserve and student+1 not in lost:
                    stack[student-1] = 1
                    reserve.remove(student+1)
            
        else:
            stack[student-1] = 1  
            
    return stack.count(1)

⭐ 힌트 풀이 (1) : 맨앞과 맨뒤에 임의의 칸을 만들어 인덱스를 쉽게 처리하는 방법!

def solution(n, lost, reserve):
	
    uniform = [1] * (n+2)
    
    for r in reserve:
    	uniform[r] += 1
    
    for l in lost:
    	uniform[l] -= 1
    
    for i in range(1, n+1):
    	if uniform[i-1] == 0 and uniform == 2:	# 앞 확인
        	uniform[i-1:i+1] = [1, 1]
        elif uniform[i] == 2 and uniform[i+1] == 0:		# 뒤 확인
        	uniform[i:i+2] = [1, 1]
     	
        return len([x for x in uniform[1:-1] if x > 0])		# 임의처리한 맨앞, 맨뒤 제외하고 count

⭐ 힌트 풀이 (2) : 집합과 정렬을 활용하여 탐욕법을 구현하는 방법!

def solution(n, lost, reserve):
	
    s = set(lost) & set(reserve)	# 전체 학생
    l = set(lost) - s	# 체육복을 가져오지 않은 학생
    r = set(reserve) - s	#체육복을 빌려줄 수 있는 학생
    
    for x in sorted(r):
    	if x-1 in l:
        	l.remove(x-1)
        elif x+1 in l:
        	l.remove(x+1)
    
    return n - len(l)