출처 : programmers.co.kr/learn/courses/30/lessons/42862#
코딩테스트 연습 - 체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번
programmers.co.kr
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 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):
and_set=set(lost)&set(reserve)
lost_set=set(lost)-and_set
reserve_set=set(reserve)-and_set
for r in reserve_set :
if r-1 in lost_set :
lost_set.remove(r-1)
elif r+1 in lost_set :
lost_set.remove(r+1)
return n-len(lost_set)set을 사용
시간복잡도는 상수 시간
lost와 reserve의 교집합을 구하고 중복을 제거한 집합 lost_set, reserve_set을 구함
여벌의 체육복을 가진 reserve_set의 왼쪽과 오른쪽 값이 체유복을 도난당한 lost_set에 있는지 본다.
def solution(n, lost, reserve):
s_lost=list(set(lost)-set(reserve)) # 중복을 제거한 값을 s_lost에 할당
s_reserve=list(set(reserve)-set(lost))
answer=n-len(s_lost) # 체육복을 가진 사람 수
if len(s_reserve)==0: # 여벌의 체육복을 가진 사람이 없다면 for문 돌릴 필요없음
return answer
for l in s_lost:
if l-1 in s_reserve: # 체육복을 잃어버린 사람의 앞사람 살피기
answer+=1
s_reserve.remove(l-1) # 빌려줬으므로 해당 값 삭제
elif l+1 in s_reserve: # 뒷사람 살피기
answer+=1
s_reserve.remove(l+1)
return answer
처음에 '여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.'는 조건을 고려하지 않고 코드를 짜서 3개 정도 실패로 떴었다.
여벌 체육복을 가져온 학생이 도난당했는지 확인하기 위해서 중복을 제거해야겠다고 생각했다. 중복을 제거하면 s_lost에는 체육복을 빌려야하는 사람, s_reserve는 체육복을 빌려줄 수 있는 사람이 남는다.
temp에 전체 사람 수 n에서 체육복을 빌려야하는 사람을 빼면 체육복을 가지고 있는 사람 수가 나온다.
이때 s_reserve의 길이가 0이면 for문을 검사할 필요가 없어서 바로 return시켰다.
for문으로 s_lost의 원소들을 반복하며 앞뒤로 여벌의 체육복을 가진 사람이 있는지 체크한다. true일 경우 체육복을 빌려주게 되므로 s_reserve에서 remove했다. 참고로 remove()는 리스트에서 값을 삭제하고, pop은 인덱스를 삭제한다는 차이가 있다.
🙋♀️ 다시 풀어봄~
# 실패
# 전체 학생 수, 도난당한 학생들 번호, 여벌의 체육복이 있는 학생
def solution(n, lost, reserve):
answer=n
clothe=[1]*n # 처음에 1벌씩 가지고 있다고 가정
# 잃어버린 사람들 기록
for l in lost :
clothe[l-1]-=1
# 여벌을 가지고 있는 사람들 기록
for r in reserve :
clothe[r-1]+=1
answer-=clothe.count(0) # 체육복을 가지고 있는 사람 수
if answer == n : # 모두 체육복을 가지고 있으면 전체 학생 리턴
return n
# 첫 번째 학생이 여벌의 옷이 있을 때
if clothe[0] > 1 and clothe[1] == 0 :
clothe[0]=1
clothe[1]=1
answer+=1
if clothe[-1] > 1 and clothe[-2] == 0 :
clothe[-1]=1
clothe[-2]=1
answer+=1
clothe=clothe[1:-1]
for i, c in enumerate(clothe) :
if c > 1 : # 여벌의 체육복
if clothe[i-1] == 0 or clothe[i+1] == 0 :
clothe[i-1]=1
clothe[i]=1
answer+=1
return answer # 체육수업을 들을 수 있는 학생의 최댓값
7번만 틀려.
# 실패
# 전체 학생 수, 도난당한 학생들 번호, 여벌의 체육복이 있는 학생
def solution(n, lost, reserve):
answer=n
clothe=[1]*n # 처음에 1벌씩 가지고 있다고 가정
# 여벌을 가지고 있는 학생만 빌려줄 수 있음.
# 잃어버린 사람들 기록
for l in lost :
clothe[l-1]-=1
# 여벌을 가지고 있는 사람들 기록
for r in reserve :
clothe[r-1]+=1
answer-=clothe.count(0) # 체육복을 가지고 있는 사람 수
if answer == n : # 모두 체육복을 가지고 있으면 전체 학생 리턴
return n
for i in reserve :
if clothe[i-1] > 1 : # 여벌의 체육복
if clothe[i-1] == 0 or clothe[i-2] == 0 :
answer+=1
return answer # 체육수업을 들을 수 있는 학생의 최댓값
3, 7, 8, 10이 틀림.
맨 처음과 끝 사람을 고려 안했다.
# 실패
# 전체 학생 수, 도난당한 학생들 번호, 여벌의 체육복이 있는 학생
def solution(n, lost, reserve):
answer=n
clothe=[1]*n # 처음에 1벌씩 가지고 있다고 가정
# 여벌을 가지고 있는 학생만 빌려줄 수 있음.
# 잃어버린 사람들 기록
for l in lost :
clothe[l-1]-=1
# 여벌을 가지고 있는 사람들 기록
for r in reserve :
clothe[r-1]+=1
answer-=clothe.count(0) # 체육복을 가지고 있는 사람 수
if answer == n : # 모두 체육복을 가지고 있으면 전체 학생 리턴
return n
for i in reserve :
if answer == n :
return n
if clothe[i-1] > 1 : # 여벌의 체육복
if i == 1 and clothe[i] == 0 : # 첫 번째 사람 고려
answer+=1
elif i == n and clothe[i-2] == 0 : # 마지막 사람 고려
answer+=1
elif clothe[i] == 0 or clothe[i-2] == 0 :
answer+=1
return answer # 체육수업을 들을 수 있는 학생의 최댓값
12번 런타임에러 뜬다.
# 실패
# 전체 학생 수, 도난당한 학생들 번호, 여벌의 체육복이 있는 학생
def solution(n, lost, reserve):
answer=n
clothe=[1]*n # 처음에 1벌씩 가지고 있다고 가정
# 잃어버린 사람들 기록
for l in lost :
clothe[l-1]-=1
# 여벌을 가지고 있는 사람들 기록
for r in reserve :
clothe[r-1]+=1
answer-=clothe.count(0) # 체육복을 가지고 있는 사람 수
if answer == n : # 모두 체육복을 가지고 있으면 전체 학생 리턴
return n
if 1 in reserve :
if clothe[0] > 1 and clothe[1] == 0 :
reserve.remove(1)
answer+=1
if n in reserve :
if clothe[-1] > 1 and clothe[-2] == 0 :
reserve.remove(n)
answer+=1
for i in reserve : # 여벌을 가지고 있는 학생만 빌려줄 수 있음.
if answer == n :
return n
if clothe[i-1] > 1 : # 여벌의 체육복
if clothe[i] == 0 or clothe[i-2] == 0 :
answer+=1
return answer # 체육수업을 들을 수 있는 학생의 최댓값
또 12번만 런타임에러 ㅠ
전처리를 좀 더 간단히 해야할 듯
다른 풀이들 보면 차집합을 많이 사용함
👨🏫 다른 사람 풀이
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)
여벌을 가진 사람의 이전 또는 다음 사람이 _lost에 있으면 체육복을 빌려준다. _lost에서 해당 사람 제거
n에서 _lost를 뺀 값을 리턴
def solution(n, lost, reserve):
reserved=0
lostN=list(set(lost)-set(reserve)) # 여벌이 없고 도난당한 사람
reserveN=list(set(reserve)-set(lost)) # 도난당하지 않은 여벌이 있는 사람
lostN.sort()
for l in lostN :
# 체육복이 없는 사람을 기준으로 이전 또는 다음 사람 중 여벌이 있는 사람 찾기
for x in range(l-1, l+2) :
if x in reserveN : # 여벌이 있는 사람
reserveN.remove(x)
reserved+=1
break
return n-len(lostN)+reserved
차집합 사용
체육복이 없는 사람의 양옆에 여벌이 있는 사람이 있는지 찾는다.
'coding test' 카테고리의 다른 글
| [파이썬] 124 나라의 숫자 (0) | 2020.11.24 |
|---|---|
| [파이썬] 같은 숫자는 싫어 (0) | 2020.11.24 |
| [파이썬] 기능개발 (0) | 2020.10.08 |
| [파이썬] 두 개 뽑아서 더하기 (0) | 2020.10.06 |
| [파이썬] 전화번호 목록 (0) | 2020.10.04 |