[프로그래머스] 땅따먹기

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

프로그래머스

 

접근

---

1. 점수의 최대값을 구해야 한다
   → DFS 접근, but 시간초과
   • 최대 4 * 3 ** 99999 개의 루트를 탐색해야 하기 때문
2. N 값이 최대 10M이므로, 0부터 N-1까지의 행을 한 번씩만 거치며 행을 순환하면서 합을 누적해나간다
   → DP 알고리즘
   
   • 모든 가능성을 고려하되, 행을 한 번씩만 거치는 것에 초점을 둬 생각해낸 방안이다

 

로직

---

• dp의 시작은 land의 0번째 인덱스가 되도록 초기화한다
• land의 행 1부터 N-1까지 반복문을 수행한다 (루프 1)
• 루프1에서 현재 dp의 값을 내림차순으로 정렬하고, 최댓값을 가지는 열 인덱스가 어디인지 확인한다
• 루프 1에서 열 인덱스 0부터 3까지 반복문을 수행한다 (루프 2)
• 루프 2에서 같은 열을 제외하고 가장 큰 누적값을 가진 dp 원소와 현재 점검 중인 행/열의 값을 더해 dp[열]를 갱신한다 
  
  • 최댓값이 같은 열인 경우만 2번째로 큰 값을 더하면 되고, 나머지는 최댓값을 더해주면 된다
• 루프1이 종료된 후, dp 값 중 최댓값을 반환한다

 

풀이

---

1. Swift 풀이

func solution(_ land:[[Int]]) -> Int{
    var dp = land[0]
    for i in 1..<land.count {
        let candidate = dp.sorted(by: { $0 > $1 })
        let candidateIndex = dp.firstIndex(of: candidate.first!)!
        for j in 0..<4 {
            let preMax = candidateIndex == j ? candidate[1] : candidate[0]
            dp[j] = land[i][j] + preMax
        }
    }
    return dp.max()!
}

 

2. Python 풀이

def solution(land):
    
    dp = land[0]
    for i in range(1, len(land)):
        
        candidate = sorted(dp, reverse=True)
        candidateIndex = dp.index(candidate[0])
        
        for j in range(4):
            preMax = candidate[1] if candidateIndex == j else candidate[0]
            dp[j] = preMax + land[i][j]
        
    return max(dp)

 

 

추가로..

원래 아래 코드를 가장 우선으로 구현했다. 하지만 효율성 테스트에서 시간 초과가 발생했다. 

최악인 경우의 시간 복잡도를 계산해봤는데, 10M * (4 + 4log4)로 1억이 나올 수가 없다고 판단했다.

enumerated를 사용하지 않고, 동일 로직에 대해 다른 방식으로 구현을 했는데 시간초과가 문제가 발생하지 않았다.

 

만약 시간 복잡도가 1억이 넘을 수가 없는데, 시간초과가 발생한다면 같은 로직이더라도 다른 풀이로 구현해보자.

 

(왜 시간초과가 나는 걸까..... )

func solution(_ land:[[Int]]) -> Int{
    var dp = land[0]
    for i in 1..<land.count {
        let candidate = dp.enumerated().sorted(by: { $0.1 > $1.1 })
        for j in 0..<4 {
            let preMax = candidate[0].0 == j ? candidate[1].1 : candidate[0].1
            dp[j] = land[i][j] + preMax
        }
    }
    return dp.max()!
}