[Swift] 2020 KAKAO BLIND RECRUITMENT 외벽 점검

 

Problem

 

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

---

Solution

 

1. Set로 된 취약점들이 담을 weaks 변수를 만들어줍니다.

 

Set로 만들어주는 이유는 취약점들이 같은 것들의 반복을 피하기 위해서입니다.(시간초과 해결하기 위해)

 

var weaks:Set<[Int]> = [weak]

 

2. 이동할 수 있는 거리가 큰 친구부터 차례로 순회한다.

 

최대한 적은 친구를 이용해야 하므로 거리가 큰 친구부터 순회합니다.

 

 for (i,d) in dist.reversed().enumerated() { ...

 

3. 이미 점검한 취약점들을 필터링한 취약점들을 새로운 취약점들에 담아줍니다.

 

weaks의 취약점들이 담긴 배열에서 취약점들을 순회해줍니다.

 

그리곤 점검되지 않은 취약점들을 필터링해줍니다.

 

만약 필터링한 취약점이 하나도 남지 않았다면 모두 점검된 것이므로 친구 숫자를 반환해줍니다.

 

아니라면 새로운 취약점들을 담는 곳에 필터링한 취약점들을 넣어줍니다.

 

weaks의 취약점들의 순회가 끝났다면 weaks를 새로운 newWeaks로 대체해줍니다.

 

func solution(_ n:Int, _ weak:[Int], _ dist:[Int]) -> Int {
    var weaks:Set<[Int]> = [weak]
    for (friendCount,d) in dist.reversed().enumerated() {
        var newWeaks:Set<[Int]> = []
        for w in weaks {
            for start in w {
                let end = (n+(start-d))%n
                let filterWeaks = start > end ? w.filter{$0 < end || start+1...n ~= $0 } : w.filter{ start+1..<end ~= $0 }
                if filterWeaks.isEmpty { return friendCount+1 }
                newWeaks.insert(filterWeaks)
            }
        }
        weaks = newWeaks
    }
    return -1
}

---

Source Code

 

---

P.S

나한테는 정말 어려웠던 문제였다...

 

처음엔 시계 반대방향과 시계방향으로 DFS 방식으로 했는데 시간 초과가 났다.

 

아무리 생각해도 모르겠어서 다른 사람 풀이를 봤는데 Set로 취약점들을 담아줘서 반복되지 않게 하는게 핵심이었다...

 

그리고 아직까지 이해는 안되는데 왜 반시계 방향으로 통일해도 답이 같은걸까..? 너무 찝찝하다...

---

참고한 블로그

 

[프로그래머스] 2020 KAKAO BLIND RECRUITMENT Coding Test 외벽 점검 Solution in Swift