오늘 풀어볼 알고리즘 문제는 프로그래머스의 '체육복'이다. 오늘도 마찬가지로 내 풀이를 먼저 적고 다른 풀이를 서술하는 방식으로 할 예정. 언어는 파이썬 사용하고 알고리즘 초보입니다ㅎㅎ. 앞으로 다양한 문제 풀고 포스트 올릴 예정이다😤.
문제는 여기!를 누르시면 풀어보실 수 있습니다.
그럼 스타뚜~👨💻
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
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명이 체육수업을 들을 수 있습니다.
처음에 든 생각은 reserve와 lost를 비교해가며 하나씩 제거해가는 방식이다. 따라서 다음과 같이 코드를 짜봤는데 결과는 FAIL.
def solution(n, lost, reserve):
for res in reserve:
if res in lost:
lost.remove(res)
reserve.remove(res)
elif res + 1 in lost:
lost.remove(res + 1)
reserve.remove(res)
elif res - 1 in lost:
lost.remove(res - 1)
reserve.remove(res)
answer = n - len(lost)
return answer
여기서 생긴 문제가 무엇인지 모르겠다... res+1과 res-1을 따져주는 순서인 것 같기도 하다.(+ 아래 해결 내용 추가)
for x in a: a.remove(x)
위 결과는 a가 [2,4]가 된다. a에서 원소를 제거하면서 for문을 돌리는 것이 오류였다.
def solution(n, lost, reserve):
for res in sorted(reserve):
if res in lost:
lost.remove(res)
reserve.remove(res)
elif res - 1 in lost:
lost.remove(res - 1)
reserve.remove(res)
elif res + 1 in lost:
lost.remove(res + 1)
reserve.remove(res)
else:
continue
answer = n - len(lost)
return answer
reserve를 정렬시키니까 테스트 케이스 1개 빼고 다 통과로 바뀌었다...마지막 케이스에 대한 풀이는 아직 모르겠다. 좀 더 고민해보고 글을 업데이트 해야겠다.
[업데이트 내용]
2차 풀이에서 생성되는 문제는 1차 풀이에서 생긴 문제와 연관되어 있다. lost와 reserve에 동시에 들어있는 학생을 먼저 처리해주어야 여벌을 가져왔지만 도난당한 학생이 여벌을 다시 빌리고 빌린 여벌을 또 빌려주는 일이 발생하지 않는다. 제일 중요한 건 for문에서 remove()하는 경우 오류가 생기는 것이다.
def solution(n, lost, reserve):
# 배열 생성
u = [1] * (n+2)
# 여벌과 도난 개수 계산
for i in reserve:
u[i] += 1
for i in lost:
u[i] -= 1
# 순서대로 체육복 빌려주기
for i in range(1, n+1):
if u[i-1] == 0 and u[i] == 2:
u[i-1:i+1] = [1,1]
elif u[i] == 2 and u[i+1] == 0:
u[i:i+2] = [1,1]
answer = len([x for x in u[1:-1] if x > 0])
return answer
하나하나 모두 살펴주는 경우이다. 학생 수가 많아지고 여벌이 있는 학생이 적을수록 비효율적인 알고리즘이 될 것이다.
def solution(n, lost, reserve):
s = set(lost) & set(reserve) #교집합
l = set(lost) - s #여벌이 있는데 도난당한 학생 제거
r = set(reserve) - s #여벌이 있고 도난 안당한 학생
for x in sorted(r):
if x-1 in l:
l.remove(x-1)
elif x+1 in l:
l.remove(x+1)
answer = n - len(l)
return answer
3-1)에서 모든 학생을 살펴보는 것과 다르게 여벌을 가져온 학생만 살펴본다.
아직 테스트 케이스를 하나 통과 못하고 있어서 좀 더 고민해보고 오류를 찾아내야겠다.