체육복
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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):
answer = 0
new_reserve = []
new_lost = []
for x in lost:
if x in reserve:
reserve.remove(x)
else:
new_lost.append(x)
lost = new_lost
answer = n - len(lost)
for x in reserve:
if x + 1 in lost:
lost.remove(x+1)
answer += 1
else:
new_reserve.append(x)
reserve = new_reserve
if not reserve or not lost:
return answer
else:
for x in reserve:
if x-1 in lost:
answer += 1
return answer🤔오답노트
11~16번 까지의 테스트케이스에서 실패가 떴다 ㅜㅜ..
이럴때 보면 테스트 케이스를 안 알려줘서 넘 짱남 흑흑...
물론 모든 케이스를 다 생각하고 짜는것이 능력이라고는 하지만 어렵당 @.@
어디서 잘못됐는지 도저히 모르겠어서 질문글을 봤고 해답을 찾았다. x + 1을 먼저 실행한게 문제였다. 단순하게 x - 1 부터 해야 옷을 빌려 입을 수 있는 학생의 최댓값이 나오는 것.
n=5
lost = [1,3]
reserve = [2,4]테스트 케이스가 이렇게 되어있다면 x + 1 부터 실행한다면 2는 3에게 옷을 빌려주게 되고 4는 1에게 옷을 빌려주지 못하게 된다. 하지만 x - 1 부터 실행한다면 2는 1에게, 4는 3에게 옷을 빌려줘서 최대값인 5를 구할 수 있다.
그래서 단순하게 x + 1 과 x - 1 의 위치만 바꿨더니 이번에는 17~20, 25 테스트 케이스에서 실패가 발생.. 아무래도 큰 수를 먼저 해도 비슷한 문제가 생기는 것 같다. 밥먹으면서 생각해보니
n=5
lost = [2,4]
reserve = [1,3]이렇게 위에랑 반대로 된다면 x - 1 부터 실행하게 된다면 1은 0이라서 안되고, 3은 2에게 옷을 빌려주게 된다. 하지만 x + 1 부터 실행을 한다면 모두에게 옷을 빌려줄 수 있는 최댓값을 구할 수 있다. 그럼 어떻게 해야할까?
✔수정코드
def solution(n, lost, reserve):
answer = 0
answer1 = 0
new_reserve = []
new_lost = []
lost1 = []
reserve1 = []
for x in lost:
if x in reserve:
reserve.remove(x)
else:
new_lost.append(x)
lost = new_lost
for x in lost:
lost1.append(x)
for x in reserve:
reserve1.append(x)
answer = n - len(lost)
answer1 = n - len(lost)
for x in reserve:
if x-1 in lost:
lost.remove(x-1)
answer += 1
else:
new_reserve.append(x)
reserve = new_reserve
for x in reserve:
if x+1 in lost:
answer += 1
# + 먼저
new_reserve = []
for x in reserve1:
if x+1 in lost1:
lost1.remove(x+1)
answer1 += 1
else:
new_reserve.append(x)
reserve1 = new_reserve
for x in reserve1:
if x-1 in lost1:
answer1 += 1
return max(answer,answer1)도저히 방법이 생각이 안나서 두 방법으로 다 구하고 나온 수를 비교하여 둘 중에 큰 수를 return 하는 방식으로 코드를 구현했다. 테스트케이스는 다 통과했지만 코드도 너무 길고 뭔가 더 효율적인 방법이 있을 것 같아서 풀었어도 푼 것 같지가 않다.. 슬픔 ㅜ
🤓다른 코드
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)와 이렇게 짧게 짤 수 있다니! 하고 감탄했지만 아무래도 이것도 결국에는 - 를 먼저 실행하는 것이다 보니 안될 것 같아서 돌려보니까 실제로 테스트 케이스 일부분에서 통과를 못했다. 아마 옛날에 테스트케이스가 더 추가되기 전의 코드인가보다. 하지만 별개로 _reserve = [r for r in reserve if r not in lost] 이 부분의 코드는 저렇게 짜는 방식을 배워야겠다. 무조건 짧게 짜는게 좋은건 아니라지만 쓸데 없이 길게 짜는것도 그렇게 좋은 방식 같지는 않다.
이 외의 나머지 코드들도 돌려봤는데 테스트케이스 몇개에서 실패했다. 아마 추가가 되어서 그런가보다. 내가 짠 코드를 더 발전 시키는 방향으로 봐야겠다.
