[코딩테스트/프로그래머스/Python]도둑질

💡생각

1. 집이 3개일 경우에는 money가 가장 많은 집의 money만 return한다.
2. 집이 짝수 개일 경우에는 홀수집의 money를 더한 것과 짝수집의 money를 더한 것을 비교해서 money값의 최댓값을 골라 return한다.
3. 집이 홀수 개일 경우에는 첫번째 집과 두번째 집, 마지막 집 3군데를 비교하여 money값이 가장 많은 집의 money를 answer에 더하고 두번째, 마지막 집을 제외하고 3개씩 묶어서 더 많은 money값의 집을 answer에 더하면서 마지막까지 반복한다.(3번째, 4번째, 5번째)

❓잘못된 코드

테스트 케이스는 통과했지만 채점을 통과하지 못함.

문제점. 코드도 너무 복잡하게 짠 것 같고 배열이 홀수일 때도 0으로 바꾼(이웃집)빼고 비교해야하는데 코드를 이상하게 짠 것 같아서 다른 사람의 코드를 보기로 함.

def solution(money):
    answer = 0
    cnt = 0
    if len(money) == 3:
        answer = max(money)
    elif len(money) % 2 == 0:
        Odd = money[0::2]
        Even =  money[1::2]
        if sum(Odd) >= sum(Even):
            answer = sum(Odd)
        else :
            answer = sum(Even)
    else :
         for i in range(-1, len(money)-1):
            if money[i] >= money[i+1]:
                answer += money[i]
                money[i] = 0
                money[i+1] = 0
                money[i-1] = 0
            else :
                answer += money[i+1]
                money[i] = 0
                money[i+1] = 0
                money[i+2] = 0
    return answer

⏬다른사람의 코드

나는 배열의 길이를 기준으로 (3일때, 홀수일때, 짝수일때) 나눠서 풀어야한다고 생각했는데 첫번째 집을 털 경우와 첫번째 집을 털지 않을 경우로 나눈다음 다 계산해본 뒤 비교해서 풀어야 하는 걸 깨달았다.

또, 다이나믹 프로그래밍에서는 dp테이블을 만들어서 푸는게 핵심인 것 같다.

🔗풀이 참고
https://inspirit941.tistory.com/161

def solution(money):
    table = [0 for _ in range(len(money))]
    
    # 첫 번째 집을 털 경우
    table[0] = money[0]
    table[1] = table[0]
    for i in range(2, len(money) - 1):
        table[i] = max(table[i-1], table[i-2] + money[i])
    value = max(table)
    
    # 첫 번째 집을 털지 않을 경우
    table = [0 for _ in range(len(money))]
    table[1] = money[1]
    for i in range(2, len(money)):
        table[i] = max(table[i-1], table[i-2] + money[i])
    return max(value, max(table))

1. money배열의 길이만큼 dp table을 만듦.
2. 첫번째 집을 털 경우와 그렇지 않을 경우로 나누어서 진행. 첫번째 집을 털었을 경우에는 마지막 집을 털 수 없기 때문에 나누어주는 것.
3. table[i]는 i번째 집까지 털었을 때 최댓값으로 정의했을 때 i-1번째 집을 털었으면 i번째 집을 털 수 없으므로 table[i]는 table[i-1]과 같고 i-1번째 집을 털지 않았으면 table[i]는 table[i-2]+money[i]의 값을 가지게 됨.
4. 마지막으로 첫번째 집을 털었을 경우(value)와 첫번째 집을 털지 않을 경우(max(table))의 값을 비교해서 더 큰 값을 return해줌.

🔗프로그래머스 - 도둑질
https://programmers.co.kr/learn/courses/30/lessons/42897