[python 파이썬][프로그래머스] 땅따먹기

https://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

 

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
		[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

---

1. 첫번째시도(실패)

• 첫행에 4개 원소로 부터 시작하여, 각행마다 max를 더하는 방향으로 하였습니다.
• 앞행에서 어떤 수가 채택되었을때, 뒷행에서 그 채택된 값의 행과 같은 행의 수는 0으로 치환합니다.
• max값이 여러개 있는 경우 뒷행의 max값을 고려하여 앞행의 값을 선택하였습니다.
• 최종적으로 가장 큰 원소가 답이 됩니다.

def solution(land):
    answer = []
    import copy
    for idx, val in enumerate(land[0]):
        result = val
        land_copy = copy.deepcopy(land[1:]) #원래 리스트 복구
        for j in range(len(land_copy)):
            land_copy[j][idx] = 0 #앞행의 같은 자리의 값이 채택되었다면 뒷행의 같은 자리의 수를 0으로 치환
            if land_copy[j].count(max(land_copy[j])) > 1 and j != len(land_copy)-1: #max값이 여러 개있는 경우
                j_max = [k for k, v in enumerate(land_copy[j]) if v == max(land_copy[j])] #max값이 있는 리스트의 자리 구하기
                for u in j_max:
                    if land_copy[j+1].index(max(land_copy[j+1])) == u: 뒷행의 최대값의 자리와 앞행의 max값의 자리가 같다면 0으로 치환하여 max값으로 채택되지 않게 한다.
                        land_copy[j][u] = 0
            result += max(land_copy[j])
            idx = land_copy[j].index(max(land_copy[j])) #채택되지 않을 수 자리 업데이트         
        answer.append(result)
    return max(answer)

- 하지만 해당 코드는 다음행까지만 고려할뿐 그다음행까지는 고려하지 못합니다.

 

 

2. 두번째시도(성공)

• n번째 행에 값들에 n-1번째 행들의 값들의 최대값을 더해줍니다.
• 같은 열에 있는 값은 제외합니다.
• 즉, 어떤 행의 각값은 그전행의 값에서 취할수 있는 최대값입니다.

 

EX)

| 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 |

인 경우

두번째 행인 [5,6,7,8]에 첫번째 행의 최대값을 더합니다.

5,6,7에는 첫번째 행의 최대값인 5이 더해지지만, 8에는 앞행에서 5가 채택되었으므로 5을 뺀 최대값인 3이 더해지므로

 

| 10 | 11 | 12 | 11 |

| 4 | 3 | 2 | 1 |

 

가 될 것입니다.

 

다음으로, 세번째 행의 4,3,1 에는 두번째 행의 최대값인 12가, 2에는 12를 제외하고 가장 큰 값인 11이 더해지므로

 

| 16 | 15 | 13 | 13 |

 

가 되어 최대값은 16이 되게 됩니다.

 

def solution(land):
    answer = 0
    for i in range(len(land)-1):
        plus = max(land[i]) 
        idx = land[i].index(max(land[i])) #현재행의 최대값의 열 위치 파악
        land[i].pop(idx) #최대값을 제외한 값을 구하기 위해 최대값 제거
        plus_sub = max(land[i]) # 같은 열에 있는 값에 더해줄 2번째 최대값
        for k in range(4):
            if k == idx: #같은 열에 있는 경우
                land[i+1][k] += plus_sub #두번째 최대값을 더해준다
            else:
                land[i+1][k] += plus #다른 열 일 경우 최대값을 더해준다.
    return max(land[-1])

 

 

3. 다른사람의 풀이

• 원리는 같지만 두번째 최대값을 구하는 측면에서 다른방법으로 접근한 풀이입니다.

 

def solution(land):
    for i in range(1, len(land)):
        for j in range(4):
            land[i][j] += max(land[i-1][0:j] + land[i-1][j+1:]) #현재값의 행보다 앞에 있는 값들과 현재행보다 뒤에있는 값들 중에서 최대값
    return max(land[-1])