[Python3] 체육복

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3#

접근법

그리디(Greedy) 알고리즘의 기초 문제이다.
학생들이 n명이라면 1번 학생부터 n번 학생까지 반복문을 돌며 체육 수업을 들을 수 있는 케이스들을 확인했다.
( 반복문 안의 k번째 학생의 케이스의 경우를 가정하면 )

1. "lost" 배열에 있지 않은 경우
2. "lost" 배열에 있는 경우
   2-1) (k-1)번째 학생이 여유분의 체육복이 있는 경우( reserve 배열에 있는 경우)
   2-2) (k+1)번째 학생이 여유분의 체육복이 있는 경우( reserve 배열에 있는 경우)

( 2번 케이스의 경우 2-1) , 2-2) 의 경우 둘 중 하나의 경우에만 속해도 정답이지만 앞선 사람에게 먼저 빌리는 것이 최선이 될 것이다. )

왜 틀렸을까?

1번 케이스의 경우 "lost" 배열에 있지 않다면 k번째 학생을 정답에 추가하였는데

k번째 학생이 "lost" 배열에 있지만 "reserve" 배열에도 있는 경우에도 정답이 될 수 있다.

작성한 코드

def solution(n, lost, reserve):
    answer = 0
    flag = [ 0 for i in range(n+1) ] 

    for num in range(1,n+1):
        if( (num not in lost) or ( num in lost and num in reserve ) ): 
            answer+=1
            continue
        if( num-1 in reserve and num-1 not in lost and flag[num-1] == 0 ):
            answer+=1
        elif( num+1 in reserve and num+1 not in lost):
            answer+=1
            flag[num+1] = 1
    return answer