[코딩테스트/Python] 프로그래머스 "체육복"

📍 문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

📍 풀이 방법

• 앞번호에게 빌려주는 경우, 뒷번호에게 빌려주는 경우를 다 따져보지 않고도 그리디하게 풀 수 있는 문제이다.
• 우선 학생 수만큼의 길이를 가지는, 모두 1로 구성된 리스트 students 를 만든다.
• lost, reserve 를 각각 순회하면서 도난 당한 학생은 1을 빼주고, 여분이 있는 학생은 1을 더해준다.
• students 의 인접한 두 요소는 총 9가지의 상태 - (0, 0), (1, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2) - 에 있을 수 있다. 이 중에서 (0, 2), (2, 0) 인 경우만 한 학생이 다른 학생에게 체육복을 빌려줄 수 있다.
• students 를 앞에서부터 훑어보면서 위의 두 상태에 있는 경우에만 체육복을 빌려준다.

def solution(n, lost, reserve):
    students = [1 for _ in range(n)]
    for l in lost:
        students[l - 1] -= 1
    for r in reserve:
        students[r - 1] += 1
    answer = 0
    for i in range(n):
        if i + 1 < n and students[i] + students[i + 1] == 2:
            students[i] = students[i + 1] = 1
        if students[i] > 0:
            answer += 1
    return answer