PROGRAMMERS Python Lv1. 체육복

이번 문제는 체육복이다.

다음의 코드로 제출했을 때 100점 중에 33점을 받았다.

def solution(n, lost, reserve):
    n_list = []
    stu = 0
    for i in range(n):
        a = i + 1
        n_list.append(a)
    add_list = sorted(lost + reserve)
    if add_list == n_list:
        stu = 5
        return stu
    for s in range(len(lost)):
        for j in range(len(reserve)):
            if lost[s] + 1 == reserve[j]:
                stu = n - len(lost) + len(reserve)
                break
            elif lost[s] - 1 == reserve[j]:
                stu = n - len(lost) + len(reserve)
                break
    return stu

문제를 푸는 순서를 다음과 같이 정리했다.

1. n을 1부터 n까지의 리스트로 만들고, reserve와 lost의 합이

만든 리스트와 같다면 5를 출력한다.

1. lost가 reserve의 사이에 있거나 1 앞뒤로 있을 경우,

체육복을 빌려줄 수 있다고 판단하여 이를 stu에 반영했다.

그렇지만 완벽하지 않은 코드이기에 다른 사람들의 풀이를 분석해보았다.

def solution(n, lost, reserve):
    set_reserve = set(reserve) - set(lost)
    set_lost = set(lost) - set(reserve)
    for i in set_reserve:
        if i-1 in set_lost:
            set_lost.remove(i-1)
        elif i+1 in set_lost:
            set_lost.remove(i+1)
    return n-len(set_lost)

이 코드의 중요한 점은 문제에서의 요구사항 중 중복이 없다는 것이다.

우선 set를 이용해서 중복값을 제거해주는 작업을 했다.

두 번째 중요한 것은 바로 체육복을 전달해주는 방향이 왼쪽 학생에게

전해져야 한다는 것이다. 이것이 바로 이 문제의 key 인 것 같다.

간단하게 여벌의 체육복을 가진 학생의 왼쪽이 lost에 들어있다면

remove를 통해 빌려준 것으로 한다.

그렇지 않을 경우 바로 오른쪽 학생에게 빌려주고 이를 마찬가지로 remove를

통해 빌려준 것으로 한다.

마지막엔 전체 n에서 체육복을 받지 못한 학생의 리스트인

set_lost의 길이를 빼주면 된다.

이번 문제는 Greedy에 관한 문제였는데,

이 Greedy Algorithm에 대한 좋은 글이 있어서

참고하면 좋을 것 같다.

https://rain-bow.tistory.com/entry/DP%EC%99%80-Greedy-Algorithm

혹시 제 풀이에 오류가 있거나

더 좋은 방법이 있다면 댓글 남겨주시면 감사드립니다.