[프로그래머스] 자물쇠와 열쇠 (Swift)

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

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

kakao 2020 블라인드 코딩테스트

key를 90도씩 회전하고 이리저리 옮겨서 lock을 풀 수 있는지 물어보는 문제

 

접근방법

lock은 고정되어있다고 생각하고 Key를 90도씩 3번 회전시키고 (회전된 키의 경우는 4개)

key를 한칸씩 옮겨가면서 Lock에 맞춰보고 풀리는지 확인해야한다.

 

그림으로 설명하면

이렇게 key를 모두 대보는 것이 접근 방법이었다.

 

시간초과가 날거라고 생각했는데 최대 크기가 20이어서 시간초과는 나지 않았다.

효율성 테스트가 있으면 lock만 보는 식으로 해서 풀어야 할듯

 

풀이 과정

1. 회전한 key를 배열에 담는다

 

2. key를 하나씩 꺼내서, 각기 다른 시작점 (사진속 좌측상단 파란박스에서 우측하단 파란박스까지 한칸씩 이동하며 모든 경우를 확인해야한다.)에 key를 넣어본 board를 구한다. (board에 key배열 값을 더하여 board 반환)

 

3. key가 적용된 board가 잠금해제가 됐는지 확인

이제 board의 각 칸에는 0,1,2의 값이 담길 수 있는데, board에서도 lock 부분만 보면 된다.

lock부분 칸의 값이 0이면 홈이 있는데 채워지지 않았다는 것 -> 잠금 해제 실패

lock부분 칸의 값이 1이면 자물쇠는 홈, 열쇠는 돌기 or 자물쇠는 돌기, 열쇠는 홈 이었다는 것 -> 잠금 해제 가능성 있음

lock부분 칸의 값이 2이면 자물쇠도 돌기, 열쇠도 돌기 였다는 것 -> 잠금 해제 실패

따라서 lock 부분의 board 칸을 모두 보면서 중간에 잠금 해제 실패로 나오지 않고

끝까지 왔다면 모두 1로 채워진 것이므로 잠금해제 성공 (아..엄청 돌려말하고 있네)

 

-> 3에서 잠금해제가 됐다고 하면 다른 key의 다른 시작점은 볼 필요가 없으므로 true 반환, 아니면 계속 ~

이렇게 회전한 키를 모두 각기 다른 시작점에서 대입해봤는데도 true로 빠지지 않았으면 이 키로는 잠금해제가 불가능한 것이므로 false 반환

 

오랜만에 tmt 설명..가독성 무엇..

 

소스코드 with 주석

import Foundation

func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
    
    let m:Int = key.count
    let n:Int = lock.count
    // lock을 정가운데에 위치시킨 board
    let board:[[Int]] = makeBoard(lock, m, n)
    // 90도씩 회전한 key들 (4개)
    let keys:[[[Int]]] = rotateKey(key)
    
    for aKey in keys {
        // startR, StartC = board에서 키의 시작점 : (0,0) ~ (board안의 lock의 마지막 지점)
        for startR in 0..<(n+m-1) {
            for startC in 0..<(n+m-1) {
                // 회전한 키를 가능한 모든 시작 점에서 잠금해제 시도
                let ongoingBoard = getBoardWithKey(aKey, board, n,m,startR, startC)
                if isUnlocked(n,m,ongoingBoard) {
                    return true
                }
            }
        }
    }
    
    return false
}

func makeBoard(_ lock:[[Int]], _ m:Int, _ n:Int) -> [[Int]] {
    // n+2*(m-1)가 한 변의 길이인 정사각형 board
    var board:[[Int]] = Array(repeating:Array(repeating:0, count:n+2*(m-1)), count: n+2*(m-1))
    // board에 lock 정중앙 위치시키기
    // lock의 시작 위치
    var sr = m-1
    var sc = m-1
    for r in 0..<n {
        for c in 0..<n {
            board[sr+r][sr+c] = lock[r][c]
        }
    }
    return board
}

func rotateKey(_ key:[[Int]]) -> [[[Int]]] {
    var result:[[[Int]]] = []
    result.append(key)

    var preKey = key
    for _ in 1..<4 {
        var rotatedKey:[[Int]] = []
        for c in 0..<key.count {
            // 세로로 한줄씩 배열에 담아 newKey에 가로 한줄로 추가
            var row:[Int] = []
            for r in 0..<key.count {
                row.append(preKey[r][c])
            }
            rotatedKey.append(row.reversed())
        }
        result.append(rotatedKey)
        preKey = rotatedKey
    }
    return result
}

func getBoardWithKey(_ key:[[Int]], _ board:[[Int]], _ n:Int, _ m:Int, _ sr:Int, _ sc:Int) -> [[Int]] {
    var board = board
    // lock이 정중앙에 있는 board에 key 넣기
    for dr in 0..<m {
        for dc in 0..<m {
            board[sr+dr][sc+dc] += key[dr][dc]
        }
    }
    return board
}

func isUnlocked(_ n:Int, _ m:Int, _ board:[[Int]]) -> Bool {
    // lock start row,col : board에서 lock이 시작하는 위치
    let lsr:Int = m-1
    let lsc:Int = m-1
    
    // unlock 확인
    for dr in 0..<n {
        for dc in 0..<n {
            if board[lsr+dr][lsc+dc] != 1 {
                return false
            }
        }
    }
    return true
}