[Kakao blind 2020]자물쇠와 열쇠

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

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

key를 돌려서 Lock에 딱 맞추면 되는 간단(?) 한 구현문제. (단, key의 전체를 사용하지 않아도 괜찮다.)

 

배열을 rotation하는 것은 손코딩으로 많이 나온다고.. 어디서 주워들었다.

그래서, rotation을 크게 2가지로 구현해보았다.

 

1. 단순 for 문으로 돌리기

규칙성이 간단하니, 구현하기는 쉽다.

M 길이의 배열이라면,

(i,j) --> (j,M-i-1)의 규칙.

def rotation(key):
    M=len(key)
    keys=[]
    keys.append(key)
    for _ in range(3):
        temp=[[0]*M for i in range(M)]
        for i in range(M):
            for j in range(M):
                temp[j][M-i-1]=key[i][j]
        keys.append(temp)
        key=temp
    return keys

2. zip 함수 이용하기.

직관적으로, colum i에 있는 원소들이 뒤집어져서 row i 로 간다. 

나름 ppt로 열심열심..ㅋㅋ

def rotation(key):
    keys=[key]
    for _ in range(3):
        temp=list(zip(*key[::-1]))
        keys.append(temp)

        key=temp
    return keys

그래서 colum 기준으로 배열을 뒤집고, 이걸 zip하면 회전이 된다.

시간이 테스트 27같은경우 절반 이상 준것을 확인할 수 있다.

 

최종코드 (zip 이용)

import copy
def rotation(key):
    keys=[key]
    for _ in range(3):
        temp=list(zip(*key[::-1]))
        keys.append(temp)

        key=temp
    return keys
def check(result):
    N=len(result)
    w=[[1]*N for i in range(N)]
    if result == w:
        return True
    return False
def solution(key, lock):
    keys=rotation(key)
    N=len(lock)
    M=len(key)-1
    answer = False
    for k in keys:
        for i in range(N+M+1):
            for j in range(N+M+1):
                print((i,j))
                lock_t=copy.deepcopy(lock)
                #겹치는 부분 변경 : 범위 : [i,i-1,...i-M][j,j-1,...,j-M]
                for idx_m,i_m in enumerate(range(i-M,i+1)):
                    if i_m>=0 and i_m<N:#do something
                        for jdx_m,j_m in enumerate(range(j-M,j+1)):
                            if j_m>=0 and j_m<N:
                                print(i_m,j_m)
                                lock_t[i_m][j_m]=lock[i_m][j_m]+k[idx_m][jdx_m]
                if check(lock_t):
                    return True


                
                
    return answer