Swift) 프로그래머스(Lv3) - 자물쇠와 열쇠 (Simulation)

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

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

안녕하세요 후르륵짭짭 입니다.

오랜만에 프로그래머스 문제 해설을 하는 거 같습니다.

사실 Lv3는 잘 풀지 못해서 여전히 문제 인거 같습니다...ㅠㅠ

풀더라도 한번에 완벽하게 풀어야 하는데,,,,

Lv3 부터는 구현도 문제 난이도도 많이 올라간 느낌을 받습니다.

 

** 문제 해설 **

이 문제는 단순 구현 문제인 것 같습니다.

처음에 이 문제를 어떻게 풀지,,, 많은 고민을 했습니다. 그래서 여러 방향을 생각하다가

못해서, 결국 해설을 봤는데요. 방법은 간단했습니다.

그냥 전체 탐색을 해버리고 90 씩 4번 돌려주는게 전부였습니다.

 

만약에 Lock이 3 * 3 이라면 아래그림 처럼 3배가 되는 크기의 새로운 보드를 만들어 줍니다.

 

 

이 보드가 바로 탐색을 위한 보드 입니다. 

Key는 무조건 Lock 보다 크기가 작기 때문에 Lock 크기의 3개만 해주면 됩니다. 그리고 아래 그림 처럼 탐색을 하게 될 겁니다.

 

 

이렇게 처음으로 걸치는 구간 부터 마지막으로 걸치는 구간까지 탐색하고 

높이를 아래쪽으로 내려서 다시 탐색하고... 이렇게 하면 됩니다.

사실 이게,,, 말이 쉽지,,, 저는 이런걸 처음 구현해봐서 사실 어려웠습니다.

 

일단 범위를 구해줘야 했습니다. Key의 크기와 Lock의 크기에 따라서 구간의 범위가 달라졌습니다.

예를 들어 

Key : 1 이고 Lock : 3 이라면 X축을 총 3번 탐색하고

Key : 2 이고 Lock : 3 이라면 X축을 총 4번을 탐색행하고

Key : 3 이고 Lock :3 이라면 X축으로 총 5번 탐색을 하게 됩니다.

즉, 어떤 규칙이 있습니다.

Key의 크기에서 1일 빼주고 그것을 Lock의 크기에 더해준 만큼 X축과 Y축을 탐색하는 거였습니다.

 

 

let cnt = key.count - 1

for y in 1...lock.count + cnt{
    
    for x in 1...lock.count + cnt{
        
        if moveKey(x: x, y : y, board, key, lock) {
           return true
        }
        
    }

따라서 위의 코드 처럼 전체를 탐색 해주면 됩니다. ( 이부분에서 많이 틀렸고 이걸 생각한다고 쫌 고생했습니다... )

 

이제 보드를 이동해주는 함수인 moveKey를 작성해야합니다. 

MoveKey 함수는 아래 처럼 새로 만들어준 보드에 숫자를 넣고 서로 더해주는 겁니다.

 

 

그런데 이때, 파랑색의 위치가 중요합니다.

Key가 2 이고 Lock이 3이라고 할때, 파랑색의 시작의 위치가 (y : 2, x :2) 입니다.

만약에 Key가 3이고 Lock이 3이라고 하면 파랑색의 시작 위치는 (1,1) 일 것 입니다.

즉, Lock의 크기에서 Key의 크기를 빼주고 + 1을 더해주면 시작 위치를 찾을 수 있는 것입니다.

시작 위치를 알았으면 끝나는 위치는 Key의 크기일 것이고 반복하면서 값을 넣어주면 됩니다.

하지만 만약 시작에서 아래 처럼 다음으로 이동했다면 

Key가 2이고 Lock이 3이라면 파랑색의 시작 위치는 (y: 2,x :3)일 것입니다. 

구간 검색을 이동한 만큼 시작 이동도 달라지는 것 입니다.

 

 

따라서 아래 처럼 MoveKey 함수를 구현할 수 있는 것 입니다.

func moveKey( x : Int, y : Int,_ board : [[Int]],_ key : [[Int]],_ lock : [[Int]]) -> Bool{
    
    var tempBoard = board
    
    let ystart = (lock.count - key.count + y)
    
    let xstart = (lock.count - key.count + x)
    
    var y = 0
    
    for yindex in ystart..<ystart + key.count{
        
        var x = 0
        
        for xindex in xstart..<xstart + key.count{
            
            
            tempBoard[yindex][xindex] += key[y][x]
            
            x += 1
        }
        
        y += 1
        
    }
    
    return checkISFit(tempBoard, lock)
}

 

ChekcISFit 함수는 자물쇠로 열수 있는지 없는지 확인해주는 것 입니다.

어렵지 않죠 ㅎㅎㅎㅎ

더했을 때 2가 있는 부분이 있다는 것은 뽈록 튀어 나온 부분 끼리 겹친다는 걸 의미하고

0이 있다는 것은 비어 있다는 것을 의미하는 것이니, 아래처럼 코드를 작성해주면 됩니다.

func checkISFit(_ board : [[Int]],_ lock :[[Int]]) -> Bool{
    
    for yindex in lock.count..<(lock.count * 2){
        
        for xindex in lock.count..<(lock.count * 2){
            
            if board[yindex][xindex] == 2 || board[yindex][xindex] == 0 {
                
                return false
            }
            
        }
        
    }
    
    return true
    
}

 

이제 마지막으로 탐색을 다 마쳤으면 회전을 해줘야합니다.

 

 

회전은 위의 그림 처럼 회전하는 것을 볼 수 있습니다.

그리고 Key가 3일 경우에 아래 처럼 모든 경우에 대해서 적어 본다면 

 

 

즉 [y][x] 라고 한다면 [x][Key크기 - y]가 되는 것을 알 수 있습니다.

따라서 회전시켜주는 함수는 아래 처럼 작성해주면 끝!!!

func rotateKey(_ key : [[Int]]) -> [[Int]]{
    
    let keysize = key.count - 1
    var tempKey : [[Int]] = Array(repeating: Array(repeating: 0, count: key.count), count: key.count)
    
    for yindex in 0..<key.count{
        
        for xindex in 0..<key.count{
            
            tempKey[xindex][keysize - yindex] = key[yindex][xindex]
            
        }
        
    }
    
    return tempKey
}

 

자 이제 끝났습니다.

이제 전체 탐색이 끝나고 나서 0 -> 90 (90)-> 90 + 90 (180) -> 90 + 90 + 90 (270)

이렇게 회전시키면서 전체를 탐색을 한다면, 정답이 나오게 됩니다!!!

나름 저의 머리로는 생각하는 것도 어려웠지만, 그래도 처음으로 2차원 배열로 구현을 해보는 경험이라

공부가 된 문제 였습니다. 

모두 즐코 하세요!!

 

- 전체 코드

func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
    
    var board : [[Int]] = Array(repeating: Array(repeating: 0, count: lock.count * 3), count: lock.count * 3)
    var key = key
    
    for yindex in lock.count..<(lock.count * 2){
        
        for xindex in lock.count..<(lock.count * 2){
            
            board[yindex][xindex] = lock[yindex - lock.count][xindex - lock.count]
            
        }
        
    }
    
    if checkISFit(board, lock) {return true}
    
    let cnt = key.count - 1
    
    for _ in 0..<4{
    
    for y in 1...lock.count + cnt{
    
    for x in 1...lock.count + cnt{
        
        if moveKey(x: x, y : y, board, key, lock) {
           return true
        }
        
    }
    
    }
        
       key = rotateKey(key)
        
    }
    
    return false
}

func moveKey( x : Int, y : Int,_ board : [[Int]],_ key : [[Int]],_ lock : [[Int]]) -> Bool{
    
    var tempBoard = board
    
    let ystart = (lock.count - key.count + y)
    
    let xstart = (lock.count - key.count + x)
    
    var y = 0
    
    for yindex in ystart..<ystart + key.count{
        
        var x = 0
        
        for xindex in xstart..<xstart + key.count{
            
            
            tempBoard[yindex][xindex] += key[y][x]
            
            x += 1
        }
        
        y += 1
        
    }
    
    return checkISFit(tempBoard, lock)
}

func checkISFit(_ board : [[Int]],_ lock :[[Int]]) -> Bool{
    
    for yindex in lock.count..<(lock.count * 2){
        
        for xindex in lock.count..<(lock.count * 2){
            
            if board[yindex][xindex] == 2 || board[yindex][xindex] == 0 {
                
                return false
            }
            
        }
        
    }
    
    return true
    
}

func rotateKey(_ key : [[Int]]) -> [[Int]]{
    
    let keysize = key.count - 1
    var tempKey : [[Int]] = Array(repeating: Array(repeating: 0, count: key.count), count: key.count)
    
    for yindex in 0..<key.count{
        
        for xindex in 0..<key.count{
            
            tempKey[xindex][keysize - yindex] = key[yindex][xindex]
            
        }
        
    }
    
    return tempKey
}