탐색_Programmers_PCCP기출 2번 퍼즐 게임 챌린지 [swift]

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

프로그래머스

문제 접근

1. 범위를 설정하고, 중간값을 사용하여 로직 조건을 만족하는지 체크한다
2. 해당 문제에서는, 중간값을 level, 해당 level을 기준으로 주어진 로직을 수행하였을 때, 사용된 시간 sum을 limit과 비교한다
3. sum이 limit을 초과 할 때, 미만일 때에 따라서 좌측 우측 범위를 변경한다.

오답 코드

문제는,,, 언제 반복문을 종료할 지를 정하기가 어려웠다.

또한, 범위의 최소값이 정답이라고 생각했으나, 최대값이 정답으로 자꾸 도출되어서? return을 최대값으로 수정하였다...

import Foundation

func solution(_ diffs:[Int], _ times:[Int], _ limit:Int64) -> Int {
    var leftPos = 1
    var rightPos = diffs.max()!
    var sol = (rightPos + 1) / 2
    
    // while 조건을 나도 모르겠네? {
    while rightPos - leftPos > 1 {
        var sum: Int64 = 0
        for (cur, different) in diffs.enumerated() {
            if different <= sol { sum += Int64(times[cur]) }
            else { sum += Int64(times[cur]) * Int64(different-sol+1) + Int64(times[cur-1]) * Int64(different-sol) }
            if sum > limit { // sum이 limit 보다 높다. sol을 올려야 함
                break 
            }
        }
        if sum > limit { // sum이 limit 보다 높다. sol을 올려야 함
            print("during sum:\(sum) overSum: ", leftPos, rightPos, sol, "new_leftPos: \(sol), new_sol = \((sol + rightPos)/2)")
                leftPos = sol
                sol = (sol + rightPos)/2
        } else { // sum이 limit에 도달하지 않았다. sol을 낮춰야 함.
            print("during sum:\(sum) lessSum: ", leftPos, rightPos, sol, "new_leftPos: \(sol), new_sol = \((leftPos + sol)/2)")
            // leftPos = sol
            // sol = (sol + rightPos)/2
            rightPos = sol
            sol = (leftPos + sol)/2   
        }
        
    }
    // print("ending: ", leftPos, rightPos, sol)
    return rightPos
}

 

오답 성능

testCase 14번에서 걸린다.

테스트 1 〉	통과 (0.11ms, 16.3MB)
테스트 2 〉	통과 (0.11ms, 16.5MB)
테스트 3 〉	통과 (0.10ms, 16.6MB)
테스트 4 〉	통과 (0.15ms, 16.4MB)
테스트 5 〉	통과 (0.15ms, 16.2MB)
테스트 6 〉	통과 (0.14ms, 16.4MB)
테스트 7 〉	통과 (0.13ms, 16.6MB)
테스트 8 〉	통과 (4.72ms, 16.3MB)
테스트 9 〉	통과 (5.74ms, 16.6MB)
테스트 10 〉	통과 (3.95ms, 16.7MB)
테스트 11 〉	통과 (9.66ms, 16.7MB)
테스트 12 〉	통과 (4.78ms, 16.5MB)
테스트 13 〉	통과 (8.43ms, 16.5MB)
테스트 14 〉	실패 (6.16ms, 16.5MB)
테스트 15 〉	통과 (1341.12ms, 42.2MB)
테스트 16 〉	통과 (1413.22ms, 42.1MB)
테스트 17 〉	통과 (1256.68ms, 42.2MB)
테스트 18 〉	통과 (1542.23ms, 42.1MB)
테스트 19 〉	통과 (1827.49ms, 42MB)
테스트 20 〉	통과 (683.14ms, 42.3MB)
테스트 21 〉	통과 (1980.65ms, 42.3MB)

 

정답 코드

크게 두가지의 수정이 있다.

외부의 큰 반복문의 조건을 변경하였다. 영원히 반복할 것.

하지만, 내부 조건에 의해서 분명히 종료하게 된다.

 

내부 반환 조건 변경

1. sum == limit인 경우. 딱맞는 값이므로, 해당 sol (level)이 조건을 만족하는 가장 작은 값이다.
2. sum > limit이다. 즉슨, sum이 limit보다 높다. level(sol)을 더 높여야한다. 이를 위해서는 leftPos를 높여야한다.
   1. 그런데, sol == leftPos인 경우, 더이상 증가 할 수 없다.
   2. 그렇다면, leftPos, rightPos의 중간값인 sol은 조건을 만족 할 수 없다. 그러므로 leftPos <= x <= rightPos범위에서 rightPos만 만족한다. 그러므로, 이를 반환한다.
3. sum < limit이면, level을 낮춰야한다. 조건을 만족하는 최소치의 level이 sol이기 때문이다. 이를 위해서는 rightPos를 줄여야한다.
   1. 그런데 sol == rightPos인 경우, 더이상 낮출 수 없다.
   2. 그렇다면, leftPos <= x <= rightPos의 범위에서 조건을 만족하고, 최소치인 leftPos를 반환한다.

import Foundation

func solution(_ diffs:[Int], _ times:[Int], _ limit:Int64) -> Int {
    var leftPos = 1
    var rightPos = diffs.max()!
    var sol = (rightPos + 1) / 2
    
    while true {
        var sum: Int64 = 0
        for (cur, different) in diffs.enumerated() {
            if different <= sol { sum += Int64(times[cur]) }
            else { sum += Int64(times[cur]) * Int64(different-sol+1) + Int64(times[cur-1]) * Int64(different-sol) }
            if sum > limit { // sum이 limit 보다 높다. sol을 올려야 함
                break 
            }
        }
        
        if sum == limit { return sol }
        else if sum > limit { // sum이 limit 보다 높다. sol을 올려야 함
            if sol == leftPos {
                print("ending: ", leftPos, rightPos, sol)
                return rightPos
            }
            leftPos = sol
            sol = (sol + rightPos)/2
        } else { // sum이 limit에 도달하지 않았다. sol을 낮춰야 함.
            if sol == rightPos { 
                print("ending: ", leftPos, rightPos, sol)
                // return sol
                return leftPos
            }
            rightPos = sol
            sol = (leftPos + sol)/2   
        }
    }
    
    return sol
}

 

뭔가 로직이 스파게티같다..

찾아본 다른 사람의 코드 중에는 1씩 가감하며 푸는 경우도 있었다.