[Swift Algorithm] 프로그래머스 60059 자물쇠와 열쇠 (2020 카카오 블라인드)

 

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

코딩테스트 연습 - 자물쇠와 열쇠

 

 

 

풀이 방법

 

자물쇠를 3배씩 영역을 늘리고

키를 90도씩 돌리니까 4가지의 키모양이 나올거에요

 

 

키

90도씩 돌린 키들

 

왜 3배를 늘리나면

 

 

이렇게 한칸씩 이동하면서 키를 넣어봐야해요

그렇기때문에 영역을 확장시켜주고

이렇게 움직이면서

 

 

딱 맞는 순간이 있다면

성공한 케이스가 되기때문이죠

 

 

문제조건을 잘봐야해요!!

저도 풀다가 놓친부분이 있어서 다시 봣어요..

 

조건

돌기끼리는 만나면 안됌

키와 자물쇠의 크기는 다를 수 있음 (키 <= 자물쇠)

 

 

열쇠를 위치를 옮겨가며 비교할때는

n-m+1 부터 시작해서 2n-1까지만 비교하면 다 비교할 수 있어요

2n-1을 넘어가면 그냥 빈공백에 더하는거라서 의미가없고 자물쇠가 엄청크고 키가작다면 비효율적인 계산이죠

 

 

 

돌기가 1 홈이 0 이기때문에

더하기로 겹치는 부분은 다 더해주고

겹친 상태에서 0혹은 2가 있다면 실패한 케이스로 취급햇어요

0이 나오는 경우는 아무것도 겹치지않았을 때

2가 나오는 경우는 돌기끼리 겹쳤을 때

이기때문에 실패케이스죠

 

검사하는 범위는

3배씩 확장했기때문에

n~2n까지의 인덱스만 검사해줬구요

 

 

 

전체적인로직은

1. 키를 돌린다

2. 겹치는 부분범위를 검사하고

3. 3배확장한 자물쇠와 키를 더한다

4. n~2n사이(진짜 자물쇠영역)에 0 혹은 2가 있다면 실패

-> 2번으로

5.1 겹치는 부분범위가 끝나도 못찾음 -> 1으로 

5.2 찾으면 리턴

 

// 열쇠를 90도 돌리고
// 자물쇠의 모서리부터 하나씩 비교하면서 체크하기
// 어케해야할지.. -> 자물쇠의 3개배크기 배열생성
// 겹치는 부분 이동하면서 완전탐색
// 돌기끼리 만나면 안됌
// 키의 크기와 자물쇠의 크기는 다를수 있음

// 2020 카카오 블라인드
// 자물쇠와 열쇠
private func solutionP60059(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
    
    let m = key.count
    let n = lock.count
    var keyList = key
    var newArr: [[Int]] = []
    var newKey: [[Int]] = []
    (1...3*n).forEach { _ in newArr.append([Int](repeating: 0, count: 3*n)) }
    (1...m).forEach { _ in newKey.append([Int](repeating: 0, count: m)) }
    
    func arrPrint(list: [[Int]]) {
        for arr in list {
            print(arr)
        }
        print("-----")
    }
    
    // 시계방향 90도회전
    func rotation(key: [[Int]]) -> [[Int]] {
        var tempKey = newKey
        for i in 0..<m {
            for j in 0..<m {
                tempKey[i][j] = key[m-1-j][i]
            }
        }
        return tempKey
    }
    
    // 3배에 자물쇠 적용
    func fetchNewArr() {
        for i in n..<2*n {
            for j in n..<2*n {
                newArr[i][j] = lock[i-n][j-n]
            }
        }
    }
    
    // 알맞는지 검사
    // 2인경우는 돌기끼리 만난경우, 0인경우는 빈칸이 있는경우
    func checkKey(lock: [[Int]]) -> Bool {
        for i in n..<2*n {
            for j in n..<2*n {
                if lock[i][j] == 0 || lock[i][j] == 2 {
                    return false
                }
            }
        }
        return true
    }
    
    // 키에 맞는지 더하기
    // row: 시작행 col: 시작열
    // 3배자물쇠에 시작점으로부터 row,col만큼 떨어진곳에서 키 맞춰보기
    func addKey(arr: inout [[Int]], row: Int, col: Int) {
        for i in 0..<m {
            for j in 0..<m {
                arr[i+row][j+col] += keyList[i%m][j%m]
            }
        }
    }
    
    fetchNewArr()
    
    for _ in 1...4 {
        keyList = rotation(key: keyList)
//        arrPrint(list: keyList)
        for i in n-m+1..<2*n { // 2n밑으로는 빈칸이라서 검사할 필요가 없음(시작점도 m-n+1위로는 할필요없음)
            for j in n-m+1..<2*n {
                var arr = newArr
                addKey(arr: &arr, row: i, col: j)
//                arrPrint(list: arr)
                if checkKey(lock: arr) {
                    return true
                }
            }
        }
    }
        
    return false
}