[Python] 프로그래머스 - 자물쇠와 열쇠

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

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

# 몇시간동안 헤매다 겨우 풀었다..

 

# 삼성기출에 자주나오는 유형과 같이 구현, 시뮬레이션 문제인데 2차원배열을 회전시키는 건 처음이어서 

   오래걸린 것 같다.

 

# M과 N이 20이하이기 때문에, 모든 key배열과 lock배열을 돌며 하나하나 검사해도 될 것이라 생각했다.

   rotate함수를 통해 key배열을 돌려주면서 lock의 모든 좌표에 끼워주면서 check함수를 통해 

   모든 자물쇠의 홈이 끼워졌는지 확인하면 된다.

   (주의할 점: lock 밖에서 일어나는 일은 신경안써도 되고, lock안에서는 자물쇠의 돌기와 열쇠의 돌기가

                  만나선 안된다. 즉, key의 1부분과 lock의 1부분이 겹쳐서는 안된다.)

 

# 자물쇠의 돌기와 열쇠의 돌기가 만나는 부분은 nlock값이 2가 된다. 또한, 열쇠와 자물쇠 홈이 만나지 않는

   부분은 nlock값이 0이 되므로 모든 자물쇠의 홈에 열쇠가 들어가고 자물쇠의 돌기와 열쇠의 돌기가 

   만나지 않는 solution의 경우는 nlock의 모든 칸이 1로 꽉 차 있다.

   따라서, check함수는 nlock의 모든 칸이 1인지 아닌지를 판단하는 함수이다. 

 

# 44, 45라인에서 반복문 범위가 0 ~ M이 아니라 -N ~ M+N인 이유는 key의 끝부분 한칸이 lock의 끝부분

  한칸과 겹쳐서 답이 되는 경우가 있기 때문에 범위를 lock의 크기보다 크게 잡아야한다.

  

 * lock과 key가 위와 같이 주어졌을 때, 아래 경우가 답이 될수 있다.

 

 

import copy

def solution(key, lock):
    # check함수: nlock배열을 매개변수로 넘겨받아 nlock의 모든 칸이 1이면 True, 하나라도 1이 아니면 False 리턴해줌.
    def check(a):
        for line in a:
            for l in line:
                if l != 1:
                    return False
        return True

    # rotate함수: key리스트를 매개변수로 넘겨받아 2차원배열 회전시킨
    def rotate(m, d):
        N = len(m)
        ret = [[0] * N for _ in range(N)]

        # d = 1 -> 시계방향으로 90도회전
        if d == 1:
            for r in range(N):
                for c in range(N):
                    ret[c][N-1-r] = m[r][c] 
        # d = 2 -> 시계방향으로 180도회전
        elif d == 2:
            for r in range(N):
                for c in range(N):
                    ret[N-1-r][N-1-c] = m[r][c]
        # d = 3 -> 시계방향으로 270도회전
        elif d == 3:
            for r in range(N):
                for c in range(N):
                    ret[N-1-c][r] = m[r][c]
        # d = 0 -> 그대로
        else:
            for r in range(N):
                for c in range(N):
                    ret[r][c] = m[r][c]

        return ret
    
    N = len(key)
    M = len(lock)
    nkey = copy.deepcopy(key)
    # key의 끝부분 한칸이 겹쳐서 정답이 될 수 있으므로 lock의 범위보다 더 크게 범위 잡음
    for i in range(-N, M+N):
        for j in range(-N, M+N):
            for r in range(4):
                # key를 90도씩 회전시키면서 lock의 모든 칸에 대입해본다.
                nlock = copy.deepcopy(lock)
                nkey = rotate(nkey, r)

                # 0부터 nkey의 범위까지 반복문을 돌며 (i+x, j+y)가 lock범위 내에 존재한다면
                # nlock[i+x][j+y]에 nkey[x][y]를 더해줌.
                # 범위 밖은 신경쓰지 않는다고 했으므로 lock범위 안에 있을때만 신경써주면 됨.
                for x in range(len(nkey)):
                    for y in range(len(nkey)):
                        if 0 <= i + x < M and 0 <= j + y < M:
                            nlock[i+x][j+y] += nkey[x][y]
                
                # check(nlock)이 True이면 return Ture, False이면 contiune를 만나 nkey를 90도 더 회전시킴
                if check(nlock):
                    return True
                else:
                    continue
    return False

(프로그래머스 level: 3)