Q10. 자물쇠와 열쇠 (2020 카카오 기출)

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 (programmers.co.kr)

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

 

전형적인 구현 문제다.

일단 음.. 2차원 배열이 나온다? 가장자리 처리가 필요한 경우가 많고 이럴 땐 padding을 주는게 정말 유용하다. 그리고 좌측상단부터 우측하단까지 iteration을 쭉 돌리면서 각 포지션마다 key를 계속 회전시켜가며 lock과 맞는지 보면 될거같다. 맞으면 key랑 lock을 더했을때 lock부분이 모두 1이 될것이다. (2가되면 돌기랑 돌기가 부딛혔다는 뜻이 될것)

 

여튼 그래서 함수를 다음과 같이 나누면 편할 것이다.

1. 회전함수

2. key랑 lock을 더하는 함수

3. 더해진 key랑 lock이 valid한지 검사하는 함수

 

일단 패딩을 진행했다.

K = len(key)
    L = len(lock)
    
    lock_pad = [[1]*(L + K*2) for _ in range(L + K*2)]
    for i in range(L):
        for j in range(L):
            lock_pad[i+L][j+L] = lock[i][j]

 

길이를 L + K*2 - 2로 하는게 맞긴한데 그냥 단순하게 구현하고 싶어서 저렇게 했다.

 

import copy

def rotate(key):
    rkey = copy.deepcopy(key)
    for row in range(len(key)):
        for col in range(len(key)):
            rkey[len(key)-col-1][row] = key[row][col]
    return rkey

def check(kl, K, L):
    for i in range(K, K+L):
        for j in range(K, K+L):
            if kl[i][j] == 2 or kl[i][j] == 0:
                return False
    return True

def klsum(key,lock,i,j):
    kl = copy.deepcopy(lock)
    for row in range(len(key)):
        for col in range(len(key)):
            kl[row+i][col+j] += key[row][col]
    return kl

def solution(key, lock):
    K = len(key)
    L = len(lock)
    
    keys = []
    for _ in range(4):
        key = rotate(key)
        keys.append(key)
    
    lock_pad = [[1]*(L + K*2) for _ in range(L + K*2)]
    for i in range(L):
        for j in range(L):
            lock_pad[i+K][j+K] = lock[i][j]
            
    for i in range(L+K):
        for j in range(L+K):
            for r in range(4):
                kl = klsum(keys[r],lock_pad, i, j)
                if check(kl, K, L):
                    return True
    
    return False

 

막 어려운 편은 아닌데 헷갈리고 실수할 수 있는 부분들이 많은 문제다.