[Algorithm] 프로그래머스 - 체육복

시작하며...

모든 알고리즘 문제 풀이는 제가 직접 짜서 정답을 맞춘 결과만을 공유합니다.

마지막 'More Solution'은 다른 정답자들 풀이 중 생각지 못했던 부분들이나 좋게 느껴진 풀이법 몇개를 가져와서 공유하였습니다.

 

[Level 1] 체육복

프로그래머스

 

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

 

My Solution

def solution(n, lost, reserve):
    # lost = sorted(lost)
    reserve = sorted(reserve)
    
    # 중복 원소 제거
    new_lost = []
    for x in lost:
        if x in reserve:
            reserve.remove(x)
        else:
            new_lost.append(x)
    lost = new_lost
    
    # 여벌옷 나눠주기
    for i in reserve:
        if i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
            
    return n-len(lost)

문제의 풀이가 위에 나와있지만 풀이하는 과정에서는 여벌옷 나눠주기 -> 중복 원소 제거 -> 정렬 순으로 문제 해결 과정이 진행되었다.

Greedy 알고리즘 풀이법을 적용해야한다고 하는데 잘 적용이 된건지는 모르겠다... ^.^

• 체육복을 빌려주는 학생들(reserve)을 전체 반복하며 가능한 경우의 수를 비교한다.
• 현재 학생인 i 의 앞번호와 뒷번호에게만 체육복을 빌려줄수 있기때문에 i - 1이 도난당한 학생 그룹(lost)에 있다면 그 학생에게 빌려주고 lost에서 삭제한다.
• 앞 번호가 없다면 뒷 번호를 다시 한번 확인하고 있다면 뒷 번호 학생에게 빌려주고 그 학생을 리스트에서 제거한다.
• 이렇게 하면 잃어버린 학생의 수가 최소가 되게 할 수 있다.
• 만약 여분을 가진 학생들이 도난까지 당했다면? lost와 reserve에 동시에 포함되는 경우이다.
• 그 학생은 다른 학생에게 빌려줄수도 없기 때문에 없는 원소로 판단하고 양쪽에서 모두 삭제해주면 된다.
• [주의] 이때 주의해야 할 점! lose와 reserve 양쪽 모두에서 remove를 진행하여 삭제한다면, 삭제후 리스트 재조정 과정에서 값이 맞지 않게 되어 에러가 발생할 수 있다.
• 그렇기때문에 한쪽에선 삭제를 진행하되 다른 한쪽은 새로운 리스트를 만들어서 추가해주는 방법으로 해결하였다.
• 이렇게 해도 테스트에서 실패가 나는 케이스가 있었다.
• 문제에서 리스트가 정렬되어 있다고 하지 않았기 때문에 체육복을 나눠줄 수 있는 학생들의 순서가 다르다면 결과가 다를수 있다. 그래서 reserve 를 정렬을 해 주면 문제가 해결된다!