[Programmers/python] 체육복

문제

Greedy

문제 흐름

Greedy 문제임을 알고 시작하니 확실히 푸는게 수월했다.
문제 유형을 알고 풀면 그 유형을 파악하며 풀게되며 배우게되는것같다.
또.. 이 문제는 사실 백준에선지 어디에선지 이미 풀어본 것 같은 느낌이었다.
문제가 익숙했다.

일단 문제를 제대로 읽지 않아 계속 제출시 일부 오답이 떴다.
확인 못했던 포인트는 아래 부분이다.

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

원래는 따로 student 배열에 체육복 수를 기록하지 않고 바로 lost와 reserve를 각각 순회하며 처리하면 불필요한 수순(입력받은 정보로 student값을 초기값 설정하는 부분)을 없애 좀더 효율적으로 처리할 수 있지 않을까? 했으나..
조건에 lost와 reserve는 오름차순으로 주어진다.라는 조건이 눈 씻고 찾아봐도 없었기에 student list로 만들게 되었다.
또 이렇게 해야만 했던 부분이 아까 놓쳤던 조건인 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우를 간단하게 확인할 수 있기 때문이다.
이렇게 미리 학생들의 체육복 수를 파악한 뒤 처리를 시작하면 깔끔하다.

student를 앞부터 하나씩 돌며 만약 본인이 0이고(체육복이 없고), 앞 친구가 2이면(체육복이 두개면),
앞 친구로부터 체육복을 빌려온다.
또한 만약 본인이 2이고(체육복이 두개고), 앞 친구가 0이면(체육복이 없으면),
앞 친구한테 체육복을 빌려온다.
앞뒤로 확인하지 않는다면 만약 맨 뒤나 맨 앞에 빌려줘야 하는 경우가 생길 경우 빌려주지 못하게 될 수도 있다.

또한 전체 학생의 수는 2명 이상 30명 이하이므로 시간복잡도는 특별히 고려하지 않고 진행했으나 O(N)이 되겠다.

코드

def solution(n, lost, reserve):
    student = [1 for i in range(n + 1)]
    for i in lost:
        student[i] -= 1
    for i in reserve:
        student[i] += 1

    answer = sum(map(lambda x: x > 0, student)) - 1
    for i in range(1, n + 1):
        if student[i] == 2 and student[i - 1] == 0:
            student[i] = 1
            student[i - 1] = 1
            answer += 1
        elif student[i] == 0 and student[i - 1] == 2:
            student[i] = 1
            student[i - 1] = 1
            answer += 1
    return answer