[Swift 알고리즘] 프로그래머스(Lv.3) - 자물쇠와 열쇠 / 2020 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 자물쇠와 열쇠" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 구현입니다.

3레벨 구현은 참 어렵고 오래 걸리는 것 같습니다.

 

1. Lock을 확장 시킵니다.

처음에 어떻게 key의 구석부터 차례대로 lock과 비교할 수 있을까 고민 했었습니다.

dfs나 bfs 문제에서 테두리를 만들어 범위를 벗어나지 않게 하는 방법이 떠올랐습니다.

이를 응용해 lock 배열을 확장 시켜 padding을 주었습니다.

 

키는 자물쇠보다 작거나 같으므로 가로 세로 2배씩 늘려야 합니다.

즉, 3배의 범위를 가진 Array를 생성하고 중앙에 lock 배열 값을 삽입하면 됩니다.

 

2. Key를 끼워보며 열리는지 확인합니다.

Key를 이동하며 끼워지는지 확인합니다.

키를 꽂는 작업은 initKey( )를, 열리는지 확인하는 작업은 openLock( )를 참고하면 됩니다.

 

2-1. 키를 이동하는 범위는 겹치는 범위만 하면 됩니다.

자물쇠 범위를 확장 시켰기 때문에 키가 자물쇠보다 작다면 빈 공간에 꽂는 상황이 생깁니다.

이런 경우는 제외시키기 위해 범위 설정을 했습니다. 어차피 정사각형이기 때문에 복잡한 과정은 아닙니다.

최소: lockSize-keySize+1
최대: lockSize*2

키의 왼쪽 구석이 겹치는 범위는 lockSize-keySize+1 부터입니다.

키의 오른쪽 구석이 겹치는 범위는 lockSize*2 입니다.

자물쇠의 원소는 i+row, j+col 좌표와 비교하면 됩니다.

 

2-2. 키가 꽂히는지 확인합니다.

키를 꽂는 작업은 키의 원소와 자물쇠의 원소를 더한 값을 비교합니다.

for i in 0..<key.count {
    for j in 0..<key.count {
        lock[i+row][j+col] += key[i][j]
    }
}

 

기존 자물쇠 범위에 0이 있으면 빈 공간이 있다는 의미이고 2가 있으면 홈과 돌기가 만난 경우입니다.

for i in 0..<size {
    for j in 0..<size {
        if lock[size+i][size+j] != 1 {
            return false
        }
    }
}

 

3. 자물쇠가 열리지 않는다면 키를 회전 시켜 재도전합니다.

자물쇠가 열리지 않는다면 키를 회전 시켜 재도전 해야 합니다.

for i in 0..<width {
    for j in 0..<width {
        newKey[j][width-i-1] = key[i][j]
    }
}

그림을 그려 비교해보면 회전 코드는 쉽게 구현할 수 있습니다.

열을 순서대로 마지막 행부터 넣으면 배열이 90도 회전하게 됩니다.

이 키를 이용해 2번 로직을 수행하면 됩니다.

 

후기

3레벨 구현 문제는 무척 복잡한 것 같습니다.

그래도 이 문제는 해답이 바로 보이고 코드 구현이 복잡했던 문제인데요.

만약 해답도 잘 안 보이는 구현 문제였다면 세 배로 막막했을 거 같네요.

 

감사합니다!

---

전체 코드

import Foundation

func rotation90(key: [[Int]]) -> [[Int]] {
    var newKey: [[Int]] = key
    let width = key.count
    for i in 0..<width {
        for j in 0..<width {
            newKey[j][width-i-1] = key[i][j]
        }
    }
    
    // print(newKey)
    return newKey
}

func initKey(_ key: [[Int]], lock: [[Int]], row: Int, col: Int) -> [[Int]] {
    var lock = lock
    for i in 0..<key.count {
        for j in 0..<key.count {
            lock[i+row][j+col] += key[i][j]
        }
    }
    
    return lock
}

func openLock(_ lock: [[Int]]) -> Bool {
    let size = lock.count / 3
    for i in 0..<size {
        for j in 0..<size {
            if lock[size+i][size+j] != 1 {
                return false
            }
        }
    }
    return true
}

func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
    var result = true 
    
    let keySize = key.count
    let lockSize = lock.count
    
    //lock 확장
    var bigLock: [[Int]] = Array(repeating: Array(repeating: 1, count: lock.count * 3), count: lock.count * 3)
    for i in 0..<lockSize {
        for j in 0..<lockSize {
            bigLock[lockSize+i][lockSize+j] = lock[i][j]
        }
    }
    
    var newKey = key
    for t in 0..<4 { //4번 회전
        let range = (lockSize-keySize+1)..<(lockSize*2)
        for i in range {
            for j in range {
                var copyBigLock = initKey(newKey, lock: bigLock, row: i, col: j)
                
                if openLock(copyBigLock) {
                    return true
                }
            }
        }
        
        //열 수 없으면 키 회전
        newKey = rotation90(key: newKey)  
    }
    
    return false
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.