📋 문제
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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 |
입출력 예 설명
예제 #11번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #23번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
🐍 이전 풀이(2021.05.29)
def solution(n, lost, reserve):
answer = 0
# 학생들의 체육복 개수 반환
students = []
for i in range(n):
count_clothes = 1 # 0, 1, 2
if i + 1 in reserve:
count_clothes += 1
if i + 1 in lost:
count_clothes -= 1
students.append(count_clothes)
count_attend = 0 # 수업 참여 학생 수
borrow = list(map(lambda x: 0, students)) # 각 학생별로 체육복 빌려주는 리스트
for i, count_clothes in enumerate(students):
if count_clothes > 1: # 본인의 체육복 개수가 1개 이상일 때 무조건 하나 주기
if i == 0:
borrow[i] -= 1
borrow[i + 1] += 1
elif i == n - 1:
borrow[i] -= 1
borrow[i - 1] += 1
else:
if students[i - 1] == 0:
borrow[i] -= 1
borrow[i - 1] += 1
else:
borrow[i] -= 1
borrow[i + 1] += 1
for i in range(n):
students[i] += borrow[i]
if students[i] != 0:
count_attend += 1
answer = count_attend
return answer🐍 python 풀이(2021.11.03)
- 사람당 가질 수 있는 체육복의 개수는 0, 1, 2 중에 있다.
체육복을 잃어버린 사람, 여분 체육복을 가져온 사람이 리스트로 주어지므로 잃어버려도 한개를 잃어버리고 여분을 가져와도 하나만 가져올 수 있다. - 체육복은 바로 앞과 뒤의 사람에게만 전달할 수 있다.
문제의 세번째 예시를 보면 1번부터 차례로 체육복 [2, 1, 0]개를 가지고 있다. 최종 체육복을 가지고 있는 사람이 2명뿐이므로 연속으로 전달할 수는 없다. 1번 사람이 2번에게 체육복을 주고, 2번이 원래 가지고 있던 자신의 체육복을 3번에게 줄 수 없다는 의미이다.
=> 본인이 여분 체육복을 가지고 있다고 무조건 나눠줄 수는 없다. 현재 학생을 기준으로 체육복이 없는 사람에게만 전달해야 하므로 그리디 유형이다.
def solution(n, lost, reserve):
before_clothes_list = [1] * n # 체육복 나눠주기 전 리스트
after_clothes_list = [0] * n # 체육복을 나눠준 후 리스트
# 체육복을 나눠주기 전의 개수 현황
for student in range(1, n + 1):
if student in lost:
before_clothes_list[student - 1] -= 1
if student in reserve:
before_clothes_list[student - 1] += 1
for student, clothes_count in enumerate(before_clothes_list):
if clothes_count == 0:
continue
if clothes_count == 1:
after_clothes_list[student] = 1
continue
# 여분 체육복이 있을 경우에만 처리
after_clothes_list[student] = 1
if student != 0:
if after_clothes_list[student - 1] == 0:
after_clothes_list[student - 1] = 1
continue
if student != len(before_clothes_list) - 1:
if before_clothes_list[student + 1] == 0:
after_clothes_list[student + 1] = 1
continue
return after_clothes_list.count(1)체육복을 다음 학생에게 연이어서 전달할 수 없으므로 전달하기 전 리스트, 전달한 후의 리스트를 나누어 관리하였다.
자신의 뒤에 있는 학생은 또 다른 학생에게 체육복을 받을 수 있는 가능성이 있기 때문에 앞의 학생부터 비교하였다. 앞의 학생은 더 앞에 있는 학생에게 받았을 수도 있으므로 체육복을 전달한 후의 리스트(after_clothes_list)에서 체육복 존재 여부를 판단했고 뒤의 학생은 아직 다른 학생에게 받지 않은 학생이므로 체육복을 전달하기 전 리스트(before_clothes_list)에서 원래 가지고 있었는지를 판단하였다.
다 풀고 이전 코드를 봤는데 방식이 비슷해서 당황했다ㅋㅋ
🐍 python 풀이(2022.01.24)
def solution(n, lost, reserve):
clothes = get_clothes_list(n, lost, reserve)
for i in range(n):
if clothes[i] != 2:
continue
# front
if i != 0 and clothes[i - 1] == 0:
clothes[i - 1] += 1
clothes[i] -= 1
continue
# back
if i + 1 < n and clothes[i + 1] == 0:
clothes[i + 1] += 1
clothes[i] -= 1
return n - clothes.count(0)
def get_clothes_list(n, lost, reserve):
clothes = [1] * n
# lost
for i in lost:
clothes[i - 1] -= 1
# reserve
for i in reserve:
clothes[i - 1] += 1
return clothes다시 풀어보면서 이전 코드를 더 깔끔하게 작성해봤다. 반복문에서 i가 0일 때를 제외하고 작성했더니 테스트코드가 16번부터 20번까지가 실패가 발생하여 수정하였다.
