[2020KAKAO][Python] 자물쇠와 열쇠 (구현, 완전탐색)

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

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

# 2차원 리스트 90도 회전
def rotate_90_degree(a):
    n = len(a) # 행 길이
    m = len(a[0]) # 열 길이
    new_a = [[0]*n for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            new_a[j][n-1-i] = a[i][j]
    return new_a

# 자물쇠 중앙이 전부 1인지 확인
def check(new_lock, n):
    for i in range(n):
        for j in range(n):
            if new_lock[i+n][j+n] != 1:
                return False
    return True
    
def solution(key, lock):
    answer = True
    
    m = len(key)
    n = len(lock)
    # lock을 3배한 새lock배열
    new_lock = [[0]*(n*3) for _ in range(n*3)]
    # 새로운 자물쇠의 중앙 부분에 기존 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j]
    
    # 문제에서 먼저 90도 회전후 비교, 4번 회전
    for _ in range(4):
        key = rotate_90_degree(key)
        
        for x in range(n*2):
            for y in range(n*2):
                for i in range(m):
                    for j in range(m):
                        # 자물쇠에 열쇠 넣기
                        new_lock[x+i][y+j] += key[i][j]
                # 자물쇠에 열쇠가 맞는지 확인
                if check(new_lock,n) == True:
                    return True
                # 열쇠 빼기
                for i in range(m):
                    for j in range(m):
                        # 자물쇠에 열쇠 넣기
                        new_lock[x+i][y+j] -= key[i][j] 
            
    
    return False

★idea :

N과 M의 크기가 작으므로 완전 탐색을 통해 문제를 해결

2차원 리스트를 90도 회전하는 방법

자물쇠를 열쇠에 넣기위한 for문의 범위

 

풀이 2: numpy 패키지를 이용한다

numpy는 for loop보다 더 빠른 시간에 결과를 계산(data가 크면 클 수록)

아직 numpy사용에 대한 정확한 이해는 떨어지지만 data가 많을 시에 이것도 고려 방법이 될 수 도 있다.

추가 nunpy 정보 : pythonstudy.xyz/python/article/402-numpy-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0

import numpy as np
# 2차원 리스트 90도 회전
def rotate_90_degree(a):
    n = len(a) # 행 길이
    m = len(a[0]) # 열 길이
    #new_a = [[0]*n for _ in range(m)]
    new_a = np.zeros((m,n))
    
    for i in range(n):
        for j in range(m):
            new_a[j][n-1-i] = a[i][j]
    return new_a

# 자물쇠 중앙이 전부 1인지 확인
def check(new_lock, n):
    for i in range(n):
        for j in range(n):
            if new_lock[i+n][j+n] != 1:
                return False
    return True
    
def solution(key, lock):
    answer = True
    
    m = len(key)
    n = len(lock)
    # lock을 3배한 새lock배열
    #new_lock = [[0]*(n*3) for _ in range(n*3)]
    new_lock = np.zeros((n*3,n*3))
    
    # 새로운 자물쇠의 중앙 부분에 기존 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j]
    
    # 문제에서 먼저 90도 회전후 비교, 4번 회전
    for _ in range(4):
        key = rotate_90_degree(key)
        
        for x in range(n*2):
            for y in range(n*2):
                for i in range(m):
                    for j in range(m):
                        # 자물쇠에 열쇠 넣기
                        new_lock[x+i][y+j] += key[i][j]
                # 자물쇠에 열쇠가 맞는지 확인
                if check(new_lock,n) == True:
                    return True
                # 열쇠 빼기
                for i in range(m):
                    for j in range(m):
                        # 자물쇠에 열쇠 넣기
                        new_lock[x+i][y+j] -= key[i][j] 
            
    
    return False

프로그래머스를 통해 테스트한 결과 38개의 테스트 케이스별 통과 속도는 더 크게 나오지만 전체 테스트 케이스가 끝나는 시간은 오히려 더 짧다. 뭐지?