프로그래머스 탐욕법(Greedy) 체육복
[링크]
https://school.programmers.co.kr/learn/courses/30/lessons/42862
[문제 설명]
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
[제한사항]
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
시도 1
def solution(n, lost, reserve):
for i in reserve:
# 2개 있는 사람 본인이 도난 당한 경우
if (i in lost):
lost.remove(i)
# 앞 사람에게 빌려줄 경우
elif ((i-1) in lost):
lost.remove(i-1)
# 뒷 사람에게 빌려줄 경우
elif ((i+1) in lost):
lost.remove(i+1)
answer = n - len(lost)
return answer틀린 이유 1: 정렬
문제 어디에서도 lost와 reserve가 정렬되어있다는 조건은 없다.
따라서, 정렬이 안 된 배열을 for문을 통해 순서대로 접근하다보면 순서가 꼬일 수 있다!
그러므로 정렬을 추가적으로 해준 후, 반복문을 돌려야한다.
.틀린 이유 2: 시도2와 동일
아래 시도2에서 설명하겠음.
시도 2
def solution(n, lost, reserve):
lost.sort()
reserve.sort()
# 2개 있는 사람 본인이 도난 당한 경우
for r in reserve:
if r in lost:
reserve.remove(r)
lost.remove(r)
for i in reserve:
# 앞 사람에게 빌려줄 경우
if ((i-1) in lost):
lost.remove(i-1)
# 뒷 사람에게 빌려줄 경우
elif ((i+1) in lost):
lost.remove(i+1)
answer = n - len(lost)
return answer틀린 이유 2:
체육복이 두벌 있는 학생은 다른 사람이 아닌 자신이 여벌의 체육복을 입는다! 를 제대로 고려하지 못함.
나도 이 부분에서 정말 오랫동안 고민했다.
고민을 하다하다 프로그래머스의 힌트 기능을 사용해버렸ㄷr..
[힌트] https://school.programmers.co.kr/learn/courses/14743/lessons/118024
.
[문제상황]
여기에 나온 문제 중 나에게 해당하는 것은
'' 반복문 내에서 lost와 reserve 내에서 공통 원소를 제거하면 리스트의 삭제 연산이 의도와는 다르게 될 수 있다! '' 이다.
.
[설명]
for문을 통해서 index 0 부터 순회한다.
그런데, 만약 index 0 원소가 삭제되면, 뒤의 원소들이 앞으로 한 칸씩 당겨온다.
즉, index 1에 있던 것이 index 0으로 온다.
다시 말하자면, for 문은 index 0을 돌았으니 이번에는 index 1 에 가야겠다! 라고 생각하지만,
index 1의 것은 index 0으로 이미 이동한 것이다.
결과적으로 for문은 원래 index 1에 있던 원소에 접근을 하지 못한 것이다.
.
[해결]
1. index 관련 예외 처리 하기.
나는 애초에 index를 사용해서 접근을 하지 않고 각 원소에 접근하는 것으로 풀어서 이렇게 풀지는 않았다.
그런데, 이 방법은 다소 번거롭고 실수할 가능성이 많다고 프로그래머스 힌트에서 그랬다. 그래서 나는 2번째 방법을 사용하였다.
2. 새로운 배열 생성
아래의 정답 코드에 코드 있습니다 :)
정답 코드
def solution(n, lost, reserve):
# 1
lost.sort()
reserve.sort()
# 2
new_reserve = [r for r in reserve if r not in lost]
new_lost = [l for l in lost if l not in reserve]
# 3
for r in new_reserve:
if (r-1) in new_lost:
new_lost.remove(r-1)
elif (r+1) in new_lost:
new_lost.remove(r+1)
answer = n - len(new_lost)
return answer[설명]
-
정렬
우선 lost와 reserve가 정렬되어 있다는 말은 어디에도 없기 때문에,
for문을 통해서 배열에 순차적으로 접근할 생각을 가진 나는 두 배열을 정렬해줬다. -
체육복 2개인 학생 우선적으로 처리
reserve와 lost에 공통으로 있는 원소들을 제거해주었다.
제거라기 보다는 공통된 원소가 없는 각각의 배열을 새로 만들어줬다.
for문 내에서 배열 원소 삭제를 안하기 위해서! (시도2의 실수를 다시 안하려고..) -
앞 뒤 사람에게 체육복 빌려주기
앞 사람에게 먼저 빌려준다.
뒤에 있는 친구는 또 다른 사람의 앞 사람이 될 수 있기 때문이다.
lost: [4, 6]
reserve: [5, 7]
4는 5에게서만 받을 수 있지만,
6은 5와 7 모두에게 받을 수 있다.
