TIL#117 알고리즘 문제풀이

11기분과 알고리즘 이야기를 하다가 그 분이 풀고 있는 걸 나도 풀어보게 되었다. 요새 면접 준비를 한다고 뭔가 하는 일 없이 시간만 가는 느낌이었는데 오랜만에 예제를 푸니 재밌었고 공부가 더 필요하다는 것을 느꼈다😂

프로그래머스 2단계의 땅따먹기를 풀어보았다.

시간이 얼마 걸리지 않았고 예시를 대입해보니 바로 답이 나왔다. 그래서 채점하기를 눌렀는데 온통 시뻘건 색..... 문제를 너무 얕보고 단순하게 생각해버린 내 잘못이었다...😭

def solution(land):
    result = [max(land[0])]
    for i in range(len(land)-1):
        if land[i].index(max(land[i])) == land[i+1].index(max(land[i+1])):
            temp_list = sorted(land[i+1], reverse=True)
            result.append(temp_list[1])
        else:
            result.append(max(land[i+1]))
    return sum(result)

위의 코드가 처음에 푼 코드이다. 예시만 맞고 나머지는 다 틀린 결과였다. 일단 제일 큰 문제는 처음 0번째 리스트에서 최대값을 구하면 안되고 연속되는 열 없이 최대값을 구해야 하는데 나는 단순히 0번째 리스트에서 최대값을 구한 상태에서 연속되는 인덱스를 제외한 나머지에서 최대값을 구하는 방식으로 풀었다는 점이다.

내가 푼 방식으로 하게 되면

이러한 상황일 때 최대값을 구할 수 없어진다.
설명이 굉장히 잘 되어 있는 블로그를 찾았고 바로 이해가 되었다.

참고 링크

다시 한번 혼자 풀어 봐야겠다😁

# 완성된 코드
def solution(land):
    for i in range(len(land)-1):
        land[i + 1][0] += max(land[i][1], land[i][2], land[i][3])
        land[i + 1][1] += max(land[i][0], land[i][2], land[i][3])
        land[i + 1][2] += max(land[i][0], land[i][1], land[i][3])
        land[i + 1][3] += max(land[i][0], land[i][1], land[i][2])
    return max(land[-1])