프로그래머스 - 자물쇠와 열쇠(Lv.3)

OQ·2022년 4월 1일
0

프로그래머스

목록 보기
30/33

문제 링크

풀이

import Foundation

func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
    var rotatedKey = key
    
    for _ in 0..<4 {    // 4번 회전시킨다
        if canSolveLock(rotatedKey, lock) {	// 이리저리 끼워맞춰 푸는게 가능한지
            return true
        }
                     
        rotatedKey = rotate(rotatedKey)
    }
    
    return false
}

// 시계방향 키 회전
func rotate(_ key: [[Int]]) -> [[Int]] {
    let M = key.count - 1
    var rotateKey: [[Int]] = (0...M).map { _ -> [Int] in    // 일단 빈값 넣기
                                                  (0...M).map { _ in 0 }
                                                 }
    for i in 0...M {
        for j in 0...M where key[i][j] == 1 {
            rotateKey[j][M - i] = 1
        }
    }
    
    return rotateKey
}

// 모서리부터 쭉 이동시켜서 끼워맞춰본다
func canSolveLock(_ key: [[Int]], _ lock: [[Int]]) -> Bool {
    let M = lock.count + ((key.count - 1) * 2)
    for i in 0...M {
        for j in 0...M {
            let lockWithKey = combine(i, j, key, lock)
            if isPerfect(lockWithKey) {
                return true
            }
        }
    }
    
    return false
}

// 끼워맞추기
func combine(_ i: Int, _ j: Int, _ key: [[Int]], _ lock: [[Int]]) -> [[Int]] {
    let N = key.count - 1
    let M = lock.count - 1
    var lockWithKey = lock
    
    for keyI in i...i+N {
        let x = keyI - N
        if x < 0 || x > M {
            continue
        }
        
        for keyJ in j...j+N {
            let y = keyJ - N
            if y < 0 || y > M {
                continue
            }
            
            if lock[x][y] == key[keyI - i][keyJ - j] {    // 끼워맞출곳이 서로 같다면 탈출
                lockWithKey[0][0] = 0   // isPerfect()에서 빨리 탈출하기 위함
                return lockWithKey
            } else if lock[x][y] == 0 {
                lockWithKey[x][y] = 1
            }
        }
    }
    
    return lockWithKey
}

// 락이 풀렸는지 확인
func isPerfect(_ lock: [[Int]]) -> Bool {
    for colum in lock {
        for row in colum {
            if row != 1 {
                return false
            }
        }
    }
    
    return true
}

후기

문제를 어떻게 풀지 구상은 금방 마쳤지만 머리속으로 키와 락이 2차원배열로 어떻게 끼워맞춰질지 코드로 짜느라 힘들었던 문제.
반복문을 엄청타서 복잡도에서 문제가 생길까 조마조마했지만 다행히 복잡도까지 요구하는 문제는 아니었다.

profile
덕업일치 iOS 개발자

0개의 댓글