탐욕법(Greedy Algorithm)
각 단계에서의 최선의 선택이 전체적으로도 최선의 선택이길 바라는 것.(욕심)
내 풀이(1)
def solution(n, lost, reserve):
set_lost = set(lost)-set(reserve)
set_reserve = set(reserve)-set(lost)
answer = n - len(set_lost)
for i in set_reserve:
if set_reserve[i-1] == lost[i]:
reserve.pop(i-1)
answer += 1
elif reserve[i+1] == lost[i]:
reserve.pop(i+1)
answer += 1
return answer+++
lost와 reserve 사이에 중복 제거는 했지만
인덱스에서 처리 오류
그리고 pop을 저렇게 사용하는 건 불가능했다.
내 풀이(2)
def solution(n, lost, reserve):
set_lost = set(lost) - set(reserve) # 중복제거
set_reserve = set(reserve) - set(lost)
answer = n - len(set_lost) #n에서 중복제거한 set_lost를 빼주었으니 체육복 가진 set_reserve들만 먼저 answer에 추가
for i in set_reserve:
if i-1 in set_lost:
set_lost.remove(i-1) #체육복 i한테 받았으니 lost에서 아웃
answer += 1 # 체육복 가진 애 한 명 추가
elif i+1 in set_lost:
set_lost.remove(i+1) #체육복 i한테 받았으니 lost에서 아웃
answer += 1
return answer
+++
인덱스에서 처리하는 게 잘못된 것 같아서
reserve 내에서 인접한 두 lost로 바꾸어 for문을 돌렸다.
pop-> remove로 바꾸어줌
(생각해보니 Pop 왜 썼지...제일 뒤에 숫자도 아닌데)
다른 풀이
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)
+++
if r not in lost
r for r in reserve
조건을 만족하는 r로만 구성
r-1과 r+1 따로 변수를 정해줌
내 풀이와 알고리즘은 같지만 중복 제거 방법이 다르다.
Engineer