본문 바로가기
Coding Test/Python

[프로그래머스] 체육복 Python Code

by giem 2022. 8. 10.
반응형

 

이번에 풀어볼 코딩 테스트는 프로그래머스의 체육복이다.

 

레벨 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++로 풀이해보겠다.

반응형

댓글