[프로그래머스] Swift - 코딩 테스트 공부

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

프로그래머스

 

2023.11.07 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

문제 조건

• 최초 알고력(alp), 코딩력(cop)이 주어진다.
• 각 문제를 풀기 위해서는 나의 알고력, 코딩력이 해당 문제의 최소 알고력/코딩력 이상이어야 한다.
• 각 문제를 풀면 해당 문제마다 주어진 만큼의 알고력, 코딩력이 증가한다.
• 각 문제를 풀기 위한 시간도 주어지며 한 문제를 여러번 풀 수 있다.
• 문제를 풀지 않고 공부를 하면 시간당 1의 알고력 또는 코딩력을 높일 수 있다.
• 모든 문제를 풀 수 있는 알고력과 코딩력을 얻는 최단 시간을 구해야 한다.

 

최소의 시간으로 빠르게 목표하는 알고력과 코딩력까지 도달시켜야 하는 문제입니다.

 

알고력/코딩력을 증가시키는 방법은 문제 풀이와 공부가 있는데 어떤 것을 선택하냐에 따라 특정 알고력/코딩력에 도달하는 시간이 달라집니다.

따라서 이러한 모든 경우의 수를 전부 탐색해야 합니다.

전부 탐색하려면 시간이 당연히 오래 걸리게 되는데 다행히 이 문제에서는 problems의 최대 길이가 100이고 필요 알고력/코딩력의 최대 크기도 150을고 비교적 작은 값이기 때문에 반복문을 여러번 돌아도 문제가 없을 것이라고 추측할 수 있습니다.

 

물론! 탐색을 할 때 최소한의 연산으로 답을 구할 수 있는 방법을 찾아야했습니다.

이 문제는 DP를 활용하면 비교적 효율적으로 최소 시간을 구할 수 있었습니다.

 

정답을 도출하기 위해서는 알고력과 코딩력이라는 2가지 요인을 충족시켜야 하고 이 때의 최소 시간을 구해야 합니다.

따라서 dp 배열을 다음과 같이 선언했습니다. (2가지 요인이 필요 시간을 결정 짓기 때문에 2차원 배열로 만들어야 합니다.)

// dp[a][b] = 알고력 a, 코딩력 b를 갖추기 위해 사용한 최소 시간
var dp = Array(repeating: Array(repeating: Int.max, count: goalCop+1), count: goalAlp+1)

 

dp[a][b]는 알고력 a와 코딩력 b를 갖추기 위해 사용한 최소 시간을 의미합니다.

여기서 goalCop와 goalAlp는 우리가 모든 문제를 풀기 위한 최소 알고력과 코딩력을 의미합니다.

 

이제 반복문을 돌며 dp를 채워나가면 됩니다.

 

 

풀이

1. solveProblem 함수 구현

fileprivate func solveProblem(a: Int, b: Int, dp: inout [[Int]], problems: [[Int]], goalAlp: Int, goalCop: Int) {
    for problem in problems {
        let alp_req = problem[0]
        let cop_req = problem[1]
        let alp_rwd = problem[2]
        let cop_rwd = problem[3]
        let cost = problem[4]
        
        // 해당 문제를 풀지 못하는 경우는 continue
        if a < alp_req { continue }
        if b < cop_req { continue }
        
        let nextA = min(a+alp_rwd, goalAlp)
        let nextB = min(b+cop_rwd, goalCop)
        
        dp[nextA][nextB] = min(dp[nextA][nextB], dp[a][b] + cost)
    }
}

 

problems 배열을 돌며 현재 알고력(a), 코딩력(b)에서 풀 수 있는 문제를 풀었을 때 dp 배열을 업데이트 하는 함수입니다.

현재 a, b로는 문제를 풀 수 없는 경우 continue 합니다.

 

nextA와 nextB를 구하는 부분이 중요했습니다.

let nextA = min(a+alp_rwd, goalAlp) 에서 a+alp_rwd는 해당 문제를 풀었을 때 얻을 수 있는 알고력을 현재 알고력에 더한 값입니다. 이 값과 goalAlp 중에 작은 값을 nextA로 선택합니다.

nextB도 마찬가지의 과정으로 설정합니다.

 

이렇게 하는 이유는 nextA 또는 nextB가 goalAlp와 goalCop보다 커지면 안되기 때문입니다.

dp 배열의 크기가 goalAlp, goalCop  만큼이기 때문에 이를 넘어서면 index out of range 에러가 발생합니다.

어차피 goal을 넘어서는 알고력/코딩력은 모든 문제를 풀 수 있게 된다는 점에서 goalAlp, goalCop와 같은 dp 배열 공간에 업데이트해도 문제가 없습니다.

 

 

 

2. solution 함수 구현

fileprivate func solution(_ alp:Int, _ cop:Int, _ problems:[[Int]]) -> Int {
    var problems = problems
    var goalAlp = alp
    var goalCop = cop
    
    for problem in problems {
        goalAlp = max(goalAlp, problem[0])
        goalCop = max(goalCop, problem[1])
    }
    
    // 문제를 풀지 않고 공부를 해서 시간당 1의 알고력/코딩력을 키우는 경우를 추가해준다.
    problems.append([0,0,1,0,1])
    problems.append([0,0,0,1,1])
    
    // dp[a][b] = 알고력 a, 코딩력 b를 갖추기 위해 사용한 최소 시간
    var dp = Array(repeating: Array(repeating: Int.max, count: goalCop+1), count: goalAlp+1)
    dp[alp][cop] = 0
    
    for a in alp...goalAlp {
        for b in cop...goalCop {
            if a == goalAlp && b == goalCop {
                return dp[a][b]
            }

            // 현재 알고력(a)와 코딩력(b)를 투입해서 풀 수 있는 문제들을 풀었을 때의 dp 배열을 갱신
            solveProblem(a: a, b: b, dp: &dp, problems: problems, goalAlp: goalAlp, goalCop: goalCop)
        }
    }
        
    return dp[goalAlp][goalCop]
}

 

먼저 dp배열 선언을 위해 goalAlp와 goalCop를 구합니다.

• problems를 돌며 알고력/코딩력의 최댓값을 각각 저장합니다.
• 이 때 goalAlp와 goalCop의 초기값이 각각 alp, cop로 되어 있어야 core dumped 에러가 발생하지 않습니다.

let goalAlp = problems.sorted(by: { $0[0] > $1[0] }).first![0]
let goalCop = problems.sorted(by: { $0[1] > $1[1] }).first![1]

 

원래 이렇게 해서 채점을 받았는데 core dumped 에러가 발생했습니다.

원인은 초기 값으로 주어지는 alp가 goalAlp보다 큰 경우가 있습니다. (cop가 goalCop 보다 큰 경우도 마찬가지!)

이럴 경우 아래에서 for a in alp...goalAlp { } 이 실행될 때 range 에러가 발생하기 때문입니다.

 

문제에서 문제를 풀지 않고 공부를 해서 시간당 1의 알고력/코딩력을 키울 수 있다고 했는데 이 조건을 별도로 처리하지 않을 수 있도록 problems 배열에 [0,0,1,0,1], [0,0,0,1,1]을 추가해줍니다. (이건 다른 분들 코드에서 가져온 아이디어입니다.)

이렇게 하면 1의 시간에 1알고력 or 1코딩력을 키울 수 있는 문제처럼 간주될 수 있습니다.

즉, 다른 문제들과 합쳐져서 경우의 수를 탐색할 수 있는 것이죠!

 

다음에는 2차원 배열인 dp를 생성합니다.

 

이중 for문을 돌며 dp를 갱신합니다.

해당 a,b의 상태에서 풀 수 있는 문제를 찾아서 풀고 dp[nextA][nextB]를 채워나가는 형태입니다.

 

 

마무리

풀고 나서 보면 크게 어렵지 않은 것 같지만 막상 문제를 처음 읽었을 때는 감이 잘 안왔습니다.

결국 가능한 경우의 수를 다 검사하되 dp 배열에 계속 최소 시간을 저장하여 특정 알고력/코딩력을 갖추기 위한 최소 시간을 업데이트 해나가는 방식을 떠올려야 했습니다.

 

이 과정에서 problems 배열에 공부를 통해 알고력/코딩력을 증가시키는 경우를 append 해주는 아이디어도 신선했습니다.