[Swift] 2022 KAKAO TECH INTERNSHIP 코딩 테스트 공부

Problem

 

프로그래머스

---

Solution

 

해당 문제는 다이나믹 프로그래밍으로 풀어야 하는 문제이다.

 

1. 알고력과 코딩력의 최대치를 구해준다.

 

문제를 모두 풀 수 있다는 것은 알고력과 코딩력의 최대치를 얻는 다는 것이므로 미리 구해준다.

 

    var maxAlp: Int = alp
    var maxCop: Int = cop
    
    problems.forEach {
        maxAlp = max(maxAlp,$0[0])
        maxCop = max(maxCop,$0[1])
    }

 

2. dp 배열을 알고력 + 1 , 코딩력 + 1개의 이중 배열을 만들어 준다.

 

각 배열의 값은 무난히 큰 값(?)으로 설정해 준다. (Int.max를 하게 되면 뒤에 해당 값에 +1을 해줄 때 오류가 남)

 

가장 초기값은 0으로 설정해 준다.

 

    var dp: [[Int]] = Array(repeating:Array(repeating:10000,count:maxCop+1),count:maxAlp+1)
    dp[alp][cop] = 0

 

3. 최대 알고력과 최대 코딩력까지 dp의 값을 +1 하여 비교한다.

 

dp의 값을 1씩 늘려가 주며 더 작은 값으로 현재 값을 갱신해 준다.

 

    for currentAlp in alp...maxAlp {
        for currentCop in cop...maxCop {
            var minAlp = min(currentAlp+1,maxAlp)
            var minCop = min(currentCop+1,maxCop)
            dp[minAlp][currentCop] = min(dp[minAlp][currentCop],dp[currentAlp][currentCop] + 1)
            dp[currentAlp][minCop] = min(dp[currentAlp][minCop],dp[currentAlp][currentCop] + 1)
			...

 

4. 풀 수 있는 문제를 확인하여 해당 문제의 알고력 코딩력을 더한 dp 위치를 비교한다.

 

만약 현재 알고력, 코딩력이 문제의 코딩력,알고력보다 크거나 같으면 풀 수 있는 문제이므로,

 

해당 문제를 풀면 얻을 수 있는 점수를 현재 알고력, 코딩력에 더해준다.

 

최대 알고력, 코딩력을 넘어갈 수도 있으므로 그 땐 최대값으로 설정해 준다.

 

그 다음 해당 위치의 값과 비교하여 더 작은 값으로 갱신해 준다.

 

            problems.forEach { problem in
                if currentAlp >= problem[0] && currentCop >= problem[1] {
                    minAlp = min(maxAlp,currentAlp+problem[2])
                    minCop = min(maxCop,currentCop+problem[3])
                    dp[minAlp][minCop] = min(dp[minAlp][minCop],dp[currentAlp][currentCop] + problem[4])
                }
            }
        }
    }

 

5. 최대 알고력, 코딩력 위치를 반환한다.

 

    return dp[maxAlp][maxCop]

---

Result

 

 

시간 복잡도는 알고력, 코딩력의 최대값이 150, 문제의 최대값이 100이므로 O(150*150*100)이 된다.

 

공간 복잡도는 코딩력 알고력의 최대값을 저장하므로 O(150*150)이 된다.

---

Source Code

 

func solution(_ alp:Int, _ cop:Int, _ problems:[[Int]]) -> Int {
    var maxAlp: Int = alp
    var maxCop: Int = cop
    
    problems.forEach {
        maxAlp = max(maxAlp,$0[0])
        maxCop = max(maxCop,$0[1])
    }
    
    var dp: [[Int]] = Array(repeating:Array(repeating:10000,count:maxCop+1),count:maxAlp+1)
    dp[alp][cop] = 0
    
    for currentAlp in alp...maxAlp {
        for currentCop in cop...maxCop {
            var minAlp = min(currentAlp+1,maxAlp)
            var minCop = min(currentCop+1,maxCop)
            dp[minAlp][currentCop] = min(dp[minAlp][currentCop],dp[currentAlp][currentCop] + 1)
            dp[currentAlp][minCop] = min(dp[currentAlp][minCop],dp[currentAlp][currentCop] + 1)
            
            problems.forEach { problem in
                if currentAlp >= problem[0] && currentCop >= problem[1] {
                    minAlp = min(maxAlp,currentAlp+problem[2])
                    minCop = min(maxCop,currentCop+problem[3])
                    dp[minAlp][minCop] = min(dp[minAlp][minCop],dp[currentAlp][currentCop] + problem[4])
                }
            }
        }
    }
    
    return dp[maxAlp][maxCop]
}