반응형
Level 1 Greedy(탐욕법)
문제 : https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3#
첫번째 정답 코드
def solution(n, lost, reserve):
answer = 0
reserve.sort()
lost.sort()
temp = reserve[:]
for i in reserve:
if i in lost:
lost.remove(i)
temp.remove(i)
reserve = temp[:]
for i in reserve:
if lost:
for j in range(len(lost)):
if i == lost[j]-1:
lost.pop(j)
break
elif i == lost[j]+1:
lost.pop(j)
break
else:
break
answer = n - len(lost)
return answer
먼저 reserve와 lost를 모두 정렬하고 앞에서부터 낮은 번호의 학생이 빌려주게 만들었습니다.
그 후 자신의 체육복이 도난당한 경우 두 리스트에서 제외 시켰습니다.
lost를 처음부터 끝까지 탐색하며 앞 뒤 번호가 맞으면 pop(인덱스로) 빼주었습니다.
하지만 위 코드는 가독성이 좋지 않고 성능도 좋지 않아 다음과 같이 바꿔주었습니다.
두번째 정답 코드
def solution(n, lost, reserve):
answer = 0
reserve.sort()
temp = reserve[:]
for i in reserve:
if i in lost:
lost.remove(i)
temp.remove(i)
reserve = temp[:]
for i in reserve:
if lost:
if i-1 in lost:
lost.remove(i-1)
elif i+1 in lost:
lost.remove(i+1)
else:
break
answer = n - len(lost)
return answer
in을 사용해서 번호가 있는지 체크하고 정렬은 reserve만 했습니다.
결과 및 정리
처음에 레벨 1 이라서 쉽게 생각했는데 은근 반례가 보이지 않아 헤맸습니다.
여벌의 체육복을 가진 학생은 도난 당한다는 조건을 읽지 못해 많이 헤맸습니다
reserve와 lost를 모두 정렬하지 않아서 그리디적으로 풀지 않았는데 조금 더 고민해보고 반례를 스스로 찾아가며 디버깅 해보겠습니다
반응형
'ProblemSolving > Greedy' 카테고리의 다른 글
프로그래머스 단속 카메라 (파이썬) (0) | 2022.05.11 |
---|---|
프로그래머스 섬 연결하기 (파이썬), 최소 신장 트리, 크루스칼 (0) | 2022.05.11 |
백준 10610 30 (python) (0) | 2022.03.28 |