프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다.
학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.
예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다.
체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 전체 학생의 수는 2명 이상 30명 이하입니다.
- 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
- 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
n lost reserve return
5 [2, 4][1, 3, 5] 5
5 [2, 4][3] 4
3 [3][1] 2
입출력 예 설명
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
문제풀이 겸 회고
일단 문제풀이를 하기 전에 제한사항 부분에 추가해주어야 할 내용이 있다.
만약 체육복이 없는 학생의 앞뒤 학생이 모두 체육복을 가지고 있을 경우, 앞의 학생에게 체육복을 빌립니다.
위 내용 때문에 삽질하느라 꽤 시간을 버렸다... 후...
일단 최종 풀이는 아래와 같다.
def solution(n, lost, reserve):
reserve_new = set(reserve) - set(lost)
lost_new = set(lost) - set(reserve)
for i in reserve_new:
if i - 1 in lost_new:
lost_new.remove(i - 1)
elif i + 1 in lost_new:
lost_new.remove(i + 1)
answer = n - len(lost_new)
return answer이 문제에서 중요하게 봐야할 부분은 '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다.' 라는 부분이다. 여벌 체육복을 가져온 학생이 체육복을 잃어 버리면 reserve 와 lost 배열 모두에서 제외해야 한다.(자기자신만 것만 있으니까.)
그래서 처음에는 아래와 같이 코드를 작성했었다.
for k in reserve:
if k in lost:
reserve.remove(k)
lost.remove(k)근데 이렇게 코딩하고 보니 remove 때문에 반복문에서 에러가 나게 되었다. 당연한것이... 자바에서도 for 문으로 처리하려는 배열을 건드리게 되면 ConcurrentModificationException 이 발생하게 된다. 그걸 간과하고 저렇게 돌려버리고 말았으니...
그래서 방법을 찾아본 결과, set(집합)과 '-'(차집합)을 이용하여 두 배열의 중복되는 값을 제거할 수 있다는 것을 찾아냈다. 그렇게 중복 값을 빼고 테스트 결과를 돌렸는데 테스트 케이스 13,14,15,16 에서 오류가 발생하였다.
로직에는 문제가 없어 보였는데 에러라니?
여담이지만 프로그래머스는 보안을 이유로 테스트 케이스를 따로 공개하지 않는다. 그래서 어떤 케이스 때문에 오류가 나는지 전혀 알 방법이 없다. 단지 코드를 계속 수정해야할 뿐이다. 상당히 마음에 안드는 방식이다. 개발에 있어서 해당 케이스에 대한 디버깅도 중요하다고 생각하는데 디버깅을 전혀 할 수 없으니...
그렇게 삽질하다가 도저히 안돼서 질문하기 란을 찾아보는데 아래 글을 발견할 수 있었다.
링크
요약하자면 앞 뒤 사람 모두가 여분의 체육복을 갖고 있을 경우 앞사람에게 빌려야 한다는 것이다.
for i in reserve_new:
if i + 1 in lost_new:
lost_new.remove(i + 1)
elif i - 1 in lost_new:
lost_new.remove(i - 1)그렇다... for문안에서 조건의 순서가 반대로였던 것이다. 나참... 이것때문에 삽질을 얼마나 했던가
위에서는 if 문에서 i + 1 이 먼저오고 그렇지 않을 경우 i - 1 로직을 타도록 되어있다. 즉, 뒷사람거를 먼저 가져오는 것이었다.
생각해보면 앞사람것을 얻어입어야 최대한 많이 얻어 입을 수 있는거긴 한데... 뭔가 이것 때문에 삽질을 계속 한 것을 생각하면 어이가 없긴 하다.
아무튼 이렇게 하여 모든 테스트를 통과하고 문제를 풀 수 있었다.
약 한달간 문제를 안풀었다가 다시 푸니 처음으로 돌아간 느낌이라 굉장히 아쉬운 마음이 크다. 다시 조금씩 주에 한번이라도 문제를 풀도록 도전해봐야 겠다.
