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

문제

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

프로그래머스

---

문제 풀이(정답)

def solution(n, lost, reserve):
    answer = 0
    dp = [1] * (n+2)
    dp[0], dp[-1] = -1, -1
    for i in reserve:
        dp[i] += 1
    for j in lost:
        dp[j] -= 1
    # print(dp)

    for k in range(1, n+1):
        if (dp[k] == 2 and dp[k-1] == 0):
            dp[k], dp[k-1] = 1, 1
        if (dp[k] == 2 and dp[k+1] == 0):
            dp[k], dp[k+1] = 1, 1

    dp = dp[1:n+1]
    for d in dp:
        if d >= 1:
            answer += 1
    return answer

dp : 각 학생이 가진 체육복의 개수

• 기본적으로 1개씩 가지고 있다고 생각
• reverse에 있는 학생은 + 1, lost에 있는 학생은 - 1 처리 해준다.
• dp[0]과 dp[-1]은 가짜 인덱스로 인덱스 에러 방지용으로 사용한다. 그 수는 임의로 -1로 부여했다.

 

체육복을 2벌 가진 학생이 양 옆에 체육복이 없는 경우에게 빌려 줄 수 있다.

따라서 먼저 왼쪽 학생을 먼저 확인하고, 그 후 오른쪽 학생을 확인한다.

이 순서가 바뀌면 오답이 된다. 그 이유는 한 명이 두 명에게 빌려주는 걸 방지하기 위해서이다.

 

그 후 가짜 인덱스로 사용되었던 0번과 마지막 인덱스를 제거해준 후,

체육복이 1벌 이상 있는 학생의 수를 세어준다.