[프로그래머스] Lv1 - 체육복

문제

프로그래머스 코딩테스트 고득점 Kit - 탐욕법(Greedy)

• Lv 1. 체육복 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/42862

코드 구현

def solution(n, lost, reserve):
    # n번 학생은 n-1번이나 n+1번에게만 빌려줄 수 있음
    # 여벌을 가져온 학생 번호가 도난당하면 -> 못빌려줌

    can_gym = []        # 체육 수업에 들어갈 수 있는 학생
    n = n - len(lost)   # 체육복을 안잃어버린 학생 수
    
    lost = sorted(lost, reverse=True)
    reserve = sorted(reserve, reverse=True)


    # 여벌을 가져온 학생 중 도난 당해서 못빌려주는 학생 찾기
    # 빌려줄 수 있는 학생 배열에서 제거 + 도난 당한 학생 배열에서 제거 -> 못빌려주지만 자기는 수업에 들어갈 수 있으니 can_gym 배열에 추가
    for l in lost:
        if (l in reserve):
            can_gym.append(l)
            reserve[reserve.index(l)] = -1
            lost[lost.index(l)] = -1

    # 빌려줄 수 있는 학생을 찾는다면 -> 체육복을 빌린 학생은 수업 참여 가능하므로 can_gym 배열에 추가 + 빌려주었으니 빌려준 학생은 빌려줄 수 있는 학생 배열에서 제거
    for l in lost:
        if (l + 1 in reserve):
            can_gym.append(l)
            reserve.pop(reserve.index(l + 1))
        elif (l - 1 in reserve):
            can_gym.append(l)
            reserve.pop(reserve.index(l - 1))
 

    answer = n + len(can_gym)

    return answer

풀이

• 최대 학생의 값보다 적게 나와서 테스트케이스 13, 14 틀림 → 정렬을 안해주면 최대로 빌려줄 수 있는 학생 수를 구할 수 없음 → 정렬 추가해서 해결 !
  • 정렬하지 않았을 때의 반례 👉 https://school.programmers.co.kr/questions/46865
  • 내 코드에서는 정렬을 해야 모든 학생들이 최대로 체육복을 빌릴 수 있는 정답을 구할 수 있다.
• 변수 설명
  • reserve : 체육복을 빌려줄 수 있는 학생들 배열
  • lost : 체육복을 도난당한 학생들 배열
  • can_gym : 체육복을 빌려입거나 혹은 도난당했지만 여벌을 가져와서 체육 수업에 들어갈 수 있는 학생 수
• n에서 우선 도난당한 학생들의 수만큼 제거하여 기본적으로 체육복을 가지고 있는 학생 수를 구해준다. (n -= len(lost))
• 그 다음, 여벌을 가져온 학생 중 도난당한 학생은 체육복을 빌려줄 수 없기 때문에 빌려줄 수 있는 학생 배열인 reserve에서 제거한다.
  • 물론 빌리지 않아도 되므로 lost 배열에서도 제거해준다.
• 나머지 도난당한 학생들 중에서 빌려줄 수 있는 학생을 찾는다 (자기 번호 -1 또는 +1)
  • → 빌려줄 수 있는 학생을 찾았으면 빌린 학생은 can_gym 에 추가, 빌려준 학생은 reserve 배열에서 제거
• 최종적으로 기본적으로 체육복을 가지고 있는 학생들 n과 can_gym 배열에 들어있는 학생들 수를 더하여 정답으로 리턴

What I learned

여벌을 가져왔는데 도난당한 학생을 제거하는 한줄 방법

_reserve = [r for r in reserve if r not in lost]
_lost = [l for l in lost if l not in reserve]

이를 이용한 다른 사람의 정답 코드

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)

▶️ pop() vs remove() vs del
참고 : https://cryosleep.tistory.com/39, https://brownbears.tistory.com/452

pop(n)

• 인덱스를 특정하여 삭제 (n == 인덱스 값) → 반환
• 아무것도 지정하지 않으면 마지막 값 삭제 → 반환
• 시간복잡도 O(N)

remove(n)

• 특정한 값을 삭제 (n == 요소 값) → 반환 X
• 특정 값이 리스트 내에 2개 이상이 있다면 순서상 가장 앞에 있는 값 삭제 → 반환 X
• 시간복잡도 O(N)

del 리스트[n]

• 리스트의 인덱스를 특정하여 삭제 → 반환 X
• 리턴값이 없기 때문에 del이 미세하게 pop()보다 더 빠르다.
• 리스트의 범위를 지정하여 삭제도 가능
  • ex) del a[:2]

arr = [1, 2, 3, 4, 5, 100]

arr.pop()                   # 맨 마지막 요소 삭제
>>> arr = [1, 2, 3, 4, 5]

arr.pop(0)                  # 0번째 인덱스의 요소 삭제
>>> arr = [2, 3, 4, 5, 100]

arr.remove(4)               # 4인 요소 값 삭제
>>> arr = [1, 2, 3, 5, 100]

del arr[1]                  # 1번째 인덱스의 요소 삭제
>>> arr = [1, 3, 4, 5, 100]