🧩 문제 : 체육복
👩🏻💻 문제 정리
💪🏻 해결 방법
그리디 알고리즘을 이용하자 !
문제에는 다음과 같은 제한사항이 존재합니다.
체육복을 빌려줄 수 있는 학생에 속하더라도, 도난당할 수 있습니다. -> 여분 체육복을 도난 당한 경우에는 체육복을 빌려줄 수 없습니다.
따라서 저는 체육복을 빌려준다했는데 도난 당한 학생을 입력값인 lost와 reserve 에서 제외하고
빌려줄 수 있는 학생의 번호 앞뒤로 체육복을 도난 당한 학생이 존재한다면 new_lost에서 remove 시키면서
( 체육복을 앞 번호에게 빌려 주었다면 뒷 번호에게는 빌려줄 수 없게하기 위해 remove )
마지막에 전체 학생 명수에서 new_lost의 길이를 뺀 값을 return 시키는 방식으로 문제에 접근했습니다.
1️⃣ 첫번째 - 틀렸습니다
def solution(n, lost, reserve):
# 여분의 체육복이 존재하더라도 도난당했다면 빌려줄 수 없음
new_reserve = [r for r in reserve if r not in lost]
new_lost = [l for l in lost if l not in reserve]
for i in new_reserve:
if i-1 in new_lost:
new_lost.remove(i-1)
elif i+1 in new_lost:
new_lost.remove(i+1)
return n - len(new_lost)
🥲 오답노트
왜 틀렸지 왜틀렸지 하다가 .. 설마 .. 정렬을 안해서 ..? 하고 해봣는데
정렬을 안해서 였습니다! 모든 입출력 예시가 정렬되어 있다고 해서 테스트 케이스까지 정렬되어 있을거라는 생각은 no .. no ..
언제나 의심하겟습니다
2️⃣ 두번째 - 맞았습니다 🥳
def solution(n, lost, reserve):
# 여분의 체육복이 존재하더라도 도난당했다면 빌려줄 수 없음
new_reserve = [r for r in reserve if r not in lost]
new_lost = [l for l in lost if l not in reserve]
# 정렬
new_reserve.sort()
new_lost.sort()
# 중복 대여를 방지 하기 위해 remove
for i in new_reserve:
if i-1 in new_lost:
new_lost.remove(i-1)
elif i+1 in new_lost:
new_lost.remove(i+1)
return n - len(new_lost)
'알고리즘' 카테고리의 다른 글
[BOJ / Python] 25603 짱해커 이동식 (0) | 2023.02.07 |
---|---|
[프로그래머스 / Python] K번째 수 (0) | 2023.02.06 |
[BOJ / Python] 1107 리모컨 (0) | 2023.02.04 |
[BOJ / Python] 앵무새 (1) | 2023.02.01 |
[BOJ / Python] 1484 다이어트 (0) | 2023.01.30 |