[프로그래머스][KAKAO_BLIND][2020] 자물쇠와 열쇠

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

def expand(lock, M):
    N = len(lock)
    for i in range(N):
        lock[i] = [1 for _ in range(M-1)] + lock[i] + [1 for _ in range(M-1)]
    N = len(lock[0])
    lock = [[1 for _ in range(N)] for _ in range(M-1)] + lock + [[1 for _ in range(N)] for _ in range(M-1)]
    return lock

def is_done(lock, N, M):
    for i in range(M - 1, M - 1 + N):
        for j in range(M - 1, M - 1 + N):
            if lock[i][j] != 1:
                return False
    return True

def add(lock, key, r, c, M):
    for i in range(r, r+M):
        for j in range(c, c+M):
            lock[i][j] += key[i-r][j-c]

def sub(lock, key, r, c, M):
    for i in range(r, r+M):
        for j in range(c, c+M):
            lock[i][j] -= key[i-r][j-c]

def rotate(key, M):
    return [[ row[j] for row in key ] for j in range(M-1, -1, -1)]

def solution(key, lock):
    M = len(key)
    N = len(lock)
    lock = expand(lock, M)

    for d in range(4):
        key = rotate(key, M)
        for r in range(len(lock) - M + 1):
            for c in range(len(lock) - M + 1):
                add(lock, key, r, c, M)
                if is_done(lock, N, M):
                    return True
                sub(lock, key, r, c, M)
    return False

• expand
  • N-1만큼 lock의 위, 아래, 왼쪽, 오른쪽을 늘리기
  • 전체 탐색시, lock의 (0,0)과 key의 (N-1, N-1)부터 탐색 시작
• rotate
  
  • key를 반시계방향으로 돌림
• add
  • 현재 위치의 lock에 key를 더함
• is_done
  • 실제 lock 범위가 모두 1인지 확인
• sub
  • add했던 key 제거

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• 데이터 범위가 작으면 전체 탐색 고려 (3 <= N, M <= 20)
• 문제의 비효율성보다 명확한 알고리즘을 고려하자