[프로그래머스 Level 1] 체육복 / 탐욕법 / 파이썬

<문제>

 

<풀이>

def solution(n, lost, reserve):
    give = reserve.copy()
    for i in range(len(reserve)):
        if reserve[i] in lost:
            lost.remove(reserve[i])
            give.remove(reserve[i])
    check = lost.copy()
    reserve = give

    for i in range(len(reserve)):
        if reserve[i] - 1 in check:
            if len(check) != 0:
                check.remove(reserve[i]-1)
        elif reserve[i] + 1 in check:
            if len(check) != 0:
                check.remove(reserve[i]+1)
        else:
            pass

    return n - len(check)

탐욕법 알고리즘(Greedy Algorithm):

 

최적해를 구하기 위한 알고리즘이다. 해를 구하기 위한 과정을 여러 단계으로 쪼갠다 생각했을 때, 매번 가장 좋은 것을 계속 선택하는 알고리즘이다. 경우에 따라서 이렇게 구한 해가 가장 좋은 해가 아닐 수도 있다. 

 

설명:

 

문제 조건과 테스트 케이스때문에 한번에 통과하기 힘든 문제였다. 우선 .copy()를 이용해 reserve와 같은 list를 만든다. reserve랑 lost랑 겹치는 번호를 먼저 찾은 다음 삭제한다. 왜 reserve에서 안 지우고 굳이 같은 list를 만들어서 지우는가? list에서 remove가 일어나면 우선 for문 loop의 횟수(len(reserve))가 바뀐다. 그렇다고해서 길이 값을 따로 지정하면 if reserve[i]에서 index error가 생긴다. list의 element가 삭제되면서 남은 element들의 index 값도 계속 바뀌기 때문이다. 이를 방지하기 위함이다.

 

그 다음에 reserve의 element들로 lost의 번호를 커버할 수 있는지 판단한다. 이때 reserve의 번호보다 작은 번호가 lost에 있는지를 먼저 검사해야한다. 이 부분때문에 테스트5, 12를 통과하지 못한다. Test case 1번을 보면 왜 그래야하는지 알 수 있다.

 

# Test case 1 #

n = 5 / lost = [2,4] / reserve = [3,5] / 답: 5

 

# Test case 2 # 

n = 9 / lost = [2,3,4,6,9] / reserve = [3,4,5,7] / 답: 7

 

+@:

.copy()를 안쓰고 그냥 anylist = reserve를 쓰면 안 된다. python의 list는 mutable하기 때문에 문제가 생긴다.

 

## 이전 실수

def solution(n, lost, reserve):
    for i in range(len(reserve)):
        if reserve[i] in lost:
            lost.remove(reserve[i])
        elif reserve[i] - 1 in lost:
            if len(lost) != 0:
                lost.remove(reserve[i]-1)
        elif reserve[i] + 1 in lost:
            if len(lost) != 0:
                lost.remove(reserve[i]+1)
        else:
            pass

    return n - len(lost)

최대한 간단하게 코드를 짜보려고 접근하다보니 다양한 케이스들을 고려하지 못했다. 테스트 5, 7에서 통과하지 못 함.