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가 마이너스 범위까지 가는 경우를 생각하지 못했다.
이번 문제는 이런 예외나 배열의 회전 등 다양하게 응용될 소지가 많이 있을 것 같다.