[CT] 프로그래머스 - 체육복(Greedy)

📎 프로그래머스-체육복

이번에 풀어 본 문제는 프로그래머스의 체육복이라는 문제이다. LV1 문제지만 몇번이나 테스트 케이스를 통과하지 못했던 문제다.

문제의 알고리즘은 그리디(Greedy) 알고리즘이다.
먼저 내가 틀렸던 코드를 살펴보자.
.
.

❌ 실패 코드

def solution(n, lost, reserve):
    count = 0
    cloth = [0]
    for i in range(1, n + 1):
        cloth.append(1)  

    for i in reserve:
        cloth[i] += 1
    for i in lost:
        cloth[i] -= 1
    # [0,  2,0,2,0,2]
    for i in range(1, n + 1):
        if cloth[i] == 0:
            if cloth[i - 1] > 1:
                cloth[i] += 1
                cloth[i - 1] -= 1
            if i < n and cloth[i + 1] > 1:
                cloth[i] += 1
                cloth[i + 1] -= 1

    for i in cloth:
        if i > 0:
            count += 1
    return count 

문제 접근

• 먼저 첫번째 인덱스가 0인 cloth 배열을 만들었다.
• 그리고 맨 첫번째 인덱스를 제외하고, 모두 체육복이 있다고 가정하였으므로 배열에 1을 추가하였다.
• reserve(여분 체육복이 있는 사람) 이 있는 인덱스에는 배열에 +1 을 추가, lost(체육복이 없는 사람) 에는 배열에 -1을 해주었다.
• 반복문을 돌면서 배열의 인덱스가 0인 지점을 만난다면(맨 처음 인덱스는 제외), 왼쪽 오른쪽을 확인하여 배열을 재구성하도록 하였다.
• 마지막으로 cloth 배열의 인덱스가 1이상이면 count 를 증가시켜 반환시켰다.

• 하지만 대부분의 테스트케이스에서 실패하였다. 나름의 여러 시도를 해보았고, 별거 아닌 부분에서의 나의 실수를 알 수 있었다.

성공한 코드를 보며 이유를 알아보자

---

✅ 성공 코드

def solution(n, lost, reserve):
    count = 0
    cloth = [1] * (n + 1)
    for i in reserve:
        cloth[i] += 1
    for i in lost:
        cloth[i] -= 1

    for i in range(1, n + 1):
        if cloth[i] == 0:
            if cloth[i - 1] > 1:
                cloth[i] += 1
                cloth[i - 1] -= 1
            elif i < n and cloth[i + 1] > 1:
                cloth[i] += 1
                cloth[i + 1] -= 1

    for i in range(1, n+1):
        if cloth[i] > 0:
            count += 1
    return count

• 몇가지 코드가 바뀌었지만 대부분은 자잘한 리펙토링부분이다. 테스트케이스가 실패한 결정적 이유는 다음 코드에서 찾을 수 있었다.

❌ 틀렸던 코드

if cloth[i - 1] > 1:
    cloth[i] += 1
    cloth[i - 1] -= 1

if i < n and cloth[i + 1] > 1:
    cloth[i] += 1
    cloth[i + 1] -= 1

✅ 정답 코드

if cloth[i - 1] > 1:
    cloth[i] += 1
    cloth[i - 1] -= 1
    
elif i < n and cloth[i + 1] > 1:
   cloth[i] += 1
   cloth[i + 1] -= 1

• 실패한 코드에서 나는 두가지 경우 모두 if 문으로 검사를 하고 있었다. 하지만 그렇게 되면 두 조건(왼쪽 검사 , 오른쪽 검사) 모두 검사를 하게 되고, 만약 학생이 두 방향 모두에서 체육복을 빌릴 수 있는 경우라면, 두 번 빌려주는 결과가 발생하게 된다.