Programmers) Lv3 [2020카카오공채] 자물쇠와 열쇠

출처: https://programmers.co.kr/learn/courses/30/lessons/60059#qna

분류: Lv3, 2020 카카오 공채

---

접근방식

배열의 크기가 3~20 으로 범위가 크지 않기 때문에 각각의 케이스를 맞춰가면서 됩니다. 

핵심 포인트는 3가지 입니다.

1. lock 과 key 를 맞춰서 열 수 있는지 확인할 수 있어야 합니다.

2. 주어진 범위 안에서 key를 이동시킬 수 있어야 합니다.

3. key 를 회전시킬 수 있어야 합니다.

---

주의할 점은 범위를 설정할 때,

key의 끝 부분이 lock의 시작 점에 오는 점부터
key의 시작 부분이 lock의 끝 점에 오는 점까지

를 확인해야 합니다.

문제의 예처럼 key와 lock이 둘 다 (3,3) 인 배열이라면,

key의 끝 부분이 lock의 시작 점 (0,0) 에 오려면 key의 시작점이 (-2,-2) 가 되어야겠죠.
key의 시작 부분이 lock의 끝 점(2,2) 에 오려면 key의 시작점이 (2,2) 가 되면 되겠구요.

한 마디로 범위는 0 - (key.count-1) ..< (lock.count-1 ) + (key.count-1) 정도가 되겠네요. 

 

해결방법

어떻게 풀어야 할 지 감이 왔다면, 위의 1 ~ 3 까지의 접근을 각각 구현하면 됩니다.

1. lock 을 열 수 있는지 확인 ( isOpen )

모두 key가 lock에 끼워진 상태를 가정했을 때 배열이 모두 1이면 됩니다.
배열은 0과 1 뿐이므로 0이 있는지 확인합니다.

func isOpen(lock: [[Int]]) -> Bool {
    return !lock.contains { $0.contains(0) }
}

 

1-2. key 를 lock에 끼우기 ( open )

key 와 lock 그리고 전체에서 key의 시작점을 인자로 받습니다.

key의 범위를 돌면서 lock의 범위를 벗어나면 무시하고
둘다 1 로 맞물리는 점이 있다면 false 를 리턴합니다.

 

func open(key: [[Int]], lock: [[Int]], to index: (row: Int, col: Int)) -> Bool {

    let keyRange = 0..<key.count
    var insertedLock = lock
    
    for r in keyRange {
        for c in keyRange {
            let lockRow = r + index.row
            let lockCol = c + index.col

	    // lock 을 벗어나는지 확인 
            guard
                lockRow >= 0,
                lockCol >= 0,
                lockRow < lock.count,
                lockCol < lock.count
                else {
                    continue
            }
            
            // 둘다 1 이라면 맞출 수 없으므로 바로 false
            if lock[lockRow][lockCol] == 1, key[r][c] == 1 { return false }
            
            // lock은 1이고 key는 1 일 때만 맞춰짐
            guard lock[lockRow][lockCol] == 0, key[r][c] == 1 else { continue }
            
            insertedLock[lockRow][lockCol] = 1
        }
    }
    
    return isOpen(lock: insertedLock)
}

2. 범위에 맞춰서 key 이동 

범위에 맞게 open을 시도하고 중간에 맞춰지면 true를 리턴합니다.

let range = -(key.count-1)..<lock.count

for r in range {
    for c in range {
        if open(key: rotatedKey, lock: lock, to: (row: r, col: c)) {
            return true
        }
    }
}

 

3. key 회전 ( rotateRight )

오른쪽으로 90° 씩 회전시켜줍니다.

0행 -> n-1 열
1행 -> n-2 열
2행 -> n-3 열
...

로 바꿔주면 됩니다. 

행 과 열을 바꿔주고 기존의 열을 행으로 바꿔주면 됩니다.

func rotateRight(key: [[Int]]) -> [[Int]] {

    var turnedKey = [[Int]](repeating: [Int](repeating: 0, count: key.count), count: key.count)
    
    let maxKey = key.count-1
    
    for r in 0...maxKey {
        for c in 0...maxKey {
            turnedKey[c][maxKey-r] = key[r][c]
        }
    }
    
    return turnedKey
}

 

회전은 총 4번을 하면되고 회전 후에  범위에 맞춰 open 해보면 되겠죠?

전체 풀이입니다.

func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
    
    let range = -(key.count-1)..<lock.count
    var rotatedKey = key
    
    for _ in 0..<4 {
        for r in range {
            for c in range {
                if open(key: rotatedKey, lock: lock, to: (row: r, col: c)) {
                    return true
                }
            }
        }
        rotatedKey = rotateRight(key: rotatedKey)
    }
    
    return false
}

func isOpen(lock: [[Int]]) -> Bool {
    return !lock.contains { $0.contains(0) }
}

func open(key: [[Int]], lock: [[Int]], to index: (row: Int, col: Int)) -> Bool {

    let keyRange = 0..<key.count
    var insertedLock = lock
    
    for r in keyRange {
        for c in keyRange {
            let lockRow = r + index.row
            let lockCol = c + index.col

            guard
                lockRow >= 0,
                lockCol >= 0,
                lockRow < lock.count,
                lockCol < lock.count
                else {
                    continue
            }
            if lock[lockRow][lockCol] == 1, key[r][c] == 1 { return false }
            guard lock[lockRow][lockCol] == 0, key[r][c] == 1 else { continue }
            
            insertedLock[lockRow][lockCol] = 1
        }
    }
    
    return isOpen(lock: insertedLock)
}

func rotateRight(key: [[Int]]) -> [[Int]] {

    var turnedKey = [[Int]](repeating: [Int](repeating: 0, count: key.count), count: key.count)
    
    let maxKey = key.count-1
    
    for r in 0...maxKey {
        for c in 0...maxKey {
            turnedKey[c][maxKey-r] = key[r][c]
        }
    }
    
    return turnedKey
}

 

배운점

key의 시작 점이 lock의 끝 점에 오는 것까지는 생각했으니 key가 마이너스 범위까지 가는 경우를 생각하지 못했다.

이번 문제는 이런 예외나 배열의 회전 등 다양하게 응용될 소지가 많이 있을 것 같다.