
이번에 풀어볼 코딩 테스트는 프로그래머스의 체육복이다.
레벨 1이지만 테스트 케이스 오류가 계속 나서
잠깐 나의 실력에 회의감을 느끼다가 문제를 읽고 다시 풀게 된 문제다.
이 글을 읽는 분들은 이미 같은 과정을 겪었을 수도 있고
다 풀고 들어온 분들도 있을 것이지만
독해의 중요성을 다시 한 번 일깨워 준 문제라는 것은 공감할 것이다.
먼저 문제를 보겠다.
문제

오래 걸린 이유 스포 방지를 위해 접은 글로 작성하겠다.
궁금한 분들은 더보기를 누르길 바란다.
제한사항을 잘 읽어야 한다.
특히 마지막 줄
- 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
아주 중요하다 이것 때문에 약 10분을 날린 것 같다.
혹시 왜 틀렸는지 모르겠다면
아래의 테스트 케이스를 추가하면 좋을 것 같다.
5, [2,3], [2,5], 4
구현 방법
구현 로직은 사실 간단하다.
lost에 있는 항목들 중 + - 1의 범위에서 reserve에 있는 항목은 다 없애주고
전체 학생 수에서 lost의 길이를 빼주면 되는 쉬운 문제이다.
근데 허점이 있다면 그것이 바로 문제파트 에서 설명한 오래 걸린 이유이다.
이 부분은 코드에서 살펴보겠다.
Code
def solution(n, lost, reserve):
for num in reserve:
if num-1 in lost:
lost.remove(num-1)
elif num+1 in lost:
lost.remove(num+1)
return n-len(lost)
이번에 구현했던 코드다.
코드 실행에서는 잘 동작하길래 이것도 쉽군 하고
제출 후 넘어가려했는데...
테스트 케이스에서 정답이 다르다고 나왔다...
아무리 확인해도 모르겠었다.
이후 제한사항의 마지막 줄을 읽고
테스트 케이스를 추가했다.
코드에도 못 빌려주는 학생은 리스트에서 제거하도록 했다.
def solution(n, lost, reserve):
_lost = []
_reserve = []
for num in lost:
if num not in reserve:
_lost.append(num)
for num in reserve:
if num not in lost:
_reserve.append(num)
for num in _reserve:
if num-1 in _lost:
_lost.remove(num-1)
elif num+1 in _lost:
_lost.remove(num+1)
return n-len(_lost)
이렇게 하니 테스트 케이스를 통과했다.
다른 사람의 풀이
다른사람의 풀이 중 좋은 점을 찾아 조합해봤다.
def solution(n, lost, reserve):
_lost = set(lost)-set(reserve)
_reserve = set(reserve)-set(lost)
for num in _reserve:
if num-1 in _lost:
_lost.remove(num-1)
elif num+1 in _lost:
_lost.remove(num+1)
return n-len(_lost)
set을 사용해서 - 연산을 하면 중복되는 값이 빠진다.
또 다른 좋은 효과는 list의 remove는 시간 복잡도가 O(n)인데
set의 remove는 시간복잡도가 O(1)이라고 한다.
파이썬을 시작한 지 얼마 되지 않아서
자료구조의 연산 시간 복잡도까지는 몰랐었는데
앞으로 이것을 활용해서 풀어야겠다.
다음 포스트에서는
C++로 풀이해보겠다.
'Coding Test > Python' 카테고리의 다른 글
[프로그래머스] 약수의 개수와 덧셈 Python Code (0) | 2022.08.17 |
---|---|
[프로그래머스] K번째수 Python Code (0) | 2022.08.16 |
[프로그래머스] 예산 Python Code (0) | 2022.08.10 |
[프로그래머스] 없는 숫자 더하기 Python Code (0) | 2022.08.08 |
[프로그래머스] 소수 만들기 Python Code (0) | 2022.08.04 |
댓글