728x90
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42862#
난이도 : Lv.1
풀이
def solution(n, lost, reserve):
newReserve = [r for r in reserve if r not in lost]
newLost = [l for l in lost if l not in reserve]
for nr in newReserve:
if nr - 1 in newLost:
newLost.remove(nr - 1)
elif nr + 1 in newLost:
newLost.remove(nr + 1)
answer = n - len(newLost)
return answer이미 카테고리에서 Greedy 알고리즘이라고 나와있다. 그렇다면 어떻게 하면 최적의 답을 찾을 수 있는지 머리를 좀 굴리면 된다.
우선, 중복도 없고! 여벌 체육복 있는 학생도 도난당했을 수도! 가 중요하다.
저 문장을 읽으면 아 중복되는 거 찾아서 빼야겠구나~ 하는 생각이 자동으로 들기 때문ㅎㅎ
그래서 나는 서로 영향을 끼치는 거 빼서 newReserve 랑 newLost를 새로 만들었다.
그럼 이제 최적의 답을 찾는 건 쉽다. 그냥 무조건 왼쪽 사람에게 먼저 빌려주면 됨.
그리고 빌려줬으면 새lost배열에서 제거해서 최종 답 구하면 완성!
다른 풀이
#newReserve = set(reserve) - set(lost)
다른 사람 풀이를 보니, 저렇게 하는 사람들도 있더라
set 은 중복을 허용하지 않는 집합 자료형으로서 저런 식의 연산은 차집합을 뜻한다.
728x90
