[Swift Algorithm] 60062 외벽 점검 (2020 카카오 블라인드)

programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

 

풀이방법

너무너무너무너무...너무 어려웠던 문제였어요...

하다가 포기할뻔햇어요 ㅠㅠ

머리로는 알겠는데 코드로 구현이안되는... 뇌가하얘져서 바보가된기분이엿어요 (사실바보일수도잇지만..)

 

반시계와 시계방향으로 생각하는 그런 방법이잇는데

원이기때문에 같은 방법이라고 생각할 수 있기때문에 고려안해도 상관없어요

 

우선 모든 경우를 탐색해야해요

문제의 예시를보면

취약지점이 [1, 5, 6, 10] 이나와있고 n: 12라면

원이라서

10다음엔? 1이죠

이런 경우를 체크하기편하게 n을 더해줘요

5, 6, 10, 13이 되겟네요

그러면 비교할때 10 - 12 - 1 사이의 거리는 3이니까 같은 경우로 취급할 수 잇죠

 

취약지점으로 먼저시작되는 지점을 모두 검사해줄거에요

[1,5,6,10] - 1부터시작 

[5,6,10,13] - 5부터 시작

[6,10,13,17] - 6부터 시작

[10,13,17,18] - 10부터 시작

 

그리고

 

dist(검사하러가는 사람)

이사람들이 움직일때도

1칸먼저가고 3칸을가는것과

3칸을먼저가고 1칸을 가는것에는 큰차이가 있기때문에 모든경우를 찾아줘야해요

이때는 순열을 이용해서 모든 이동경우를 찾아줄거에요

 

코드를 구현하고나니

검사안한지점이 있을때 -1이라는 값을 뱉어야하는데 누락됬더라구요

배열을 이용해서 방문체크를 하려했는데 

배열을 새로만들어주는 시간이 생각보다 오래걸려서 시간초과가 나더라구요

그래서 Set을 이용해서 시간을 줄였어요

 

코드가 살짝더러워요.. 어찌어찌 짜다보니 .. 

 

로직을 간단하게 설명하자면

취약지점의 모든경우를 한번씩 검사

-> weak의 순회

 

갈수 있는 거리의 경우의수를 한번씩 검사

-> dist순열 생성후 순회

 

취약지점 수리가능한지 검사

-> weak의 처음시작지점을 dist요소를 더해가면서 체크

 

다음취약지점을 넘어간경우

-> 그 사람이 지나간 취약지점 체크, 다음 취약지점과 비교, 비교하다가 작아지면 다음지점을 시작점으로

-> 다음 취약지점과같으면 그 지점도 검사했다고 체크해야함

 

모든 지점 검사완료시 빠져나옴(효율성을위해)

 

모든 지점이 검사됬을 때만 지점 방문한 횟수 비교

 

max와 마지막의 결과값이 같은경우 검사할수없는 케이스이므로 -1리턴

 

 

// 외벽점검
private func solutionP60062(_ n:Int, _ weak:[Int], _ dist:[Int]) -> Int {
    let max = Int.max
    var result = max
    var weaks = weak
    var permutationDist: [[Int]] = []
    let visited: [Bool] = [Bool](repeating: false, count: dist.count)
    // 갈수있는 거리의 순열(모든경우 체크)
    func permutation(depth: Int, visited: [Bool], arr: [Int]) {
        if depth == dist.count {
            permutationDist.append(arr)
        }
        var visited = visited
        for i in 0..<dist.count {
            if visited[i] {
                continue
            }
            
            visited[i] = true
            permutation(depth: depth+1, visited: visited, arr: arr+[dist[i]])
            visited[i] = false
        }
    }
    permutation(depth: 0, visited: visited, arr: [])
    // 순서대로 순회
    for _ in weaks.indices {
        // 모든조합 검사
        for permutation in permutationDist {
            var count = 0 // 검사한 사람수 확인
            var visitSet = Set<Int>() // 취약지점 방문햇는지 확인
            var i = 0 // 검사하는 인덱스
            var start = weaks[i]
            let last = weaks.last!

            // 취약지점 수리가능여부검사
            for p in permutation {
                if i > weaks.count - 1 || last < start {
                    break
                }

                start += p
                count += 1
                visitSet.update(with: i)
                // 다음취약지점을 넘어간경우
                if i+1 < weaks.count && start >= weaks[i+1] {
                    // 현재사람이 지나간 취약지점까지 검사함
                    for j in i+1..<weaks.count {
                        if start < weaks[j] { // 작으면 포함하지않음
                            start = weaks[j]
                            i = j - 1
                            break
                        } else if start == weaks[j] { // 같으면 현재자리포함
                            i = j
                        }
                        visitSet.update(with: j)
                    }
                    if visitSet.count == weaks.count { // 모든지점이 검사됬을시 빠져나옴
                        break
                    }
                } else { // 다음지점 검사
                    i += 1
                    if i >= weaks.count {
                        continue
                    }
                    start = weaks[i]
                }
            }
            if visitSet.count == weaks.count { // 모든지점이 검사되지않았으면 제외
                result = min(result, count)
            }
        }
        
        let remove = weaks.removeFirst()
        weaks.append(remove+n)
    }

    return result == max ? -1 : result
}