[파이썬(python)] 구현 문제 자물쇠와 열쇠

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

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

 

내가 작성한 코드

 

def rotate(key):
    #90도 회전
    return key

def isopen(key, lock):
    #맞는지 안맞는지
    
    return 

def solution(key, lock):
    n = len(lock)
    m = len(key)
    new_lock = [[0 for _ in range(m+2*n)] for _ in range(m+2*n)]
    
    #i = m-1
    #j = m-1
    #new_lock[i][j]
    
    for i in range(n):
        for j in range(n):
            if lock[i][j] == 1:
                new_lock[i+m-1][j+m-1]=1
    
    for _ in range(4):
        if isopen(key, new_lock):
            return True
        else:
            key = rotate(key)
    print(new_lock)
    return False

 

뭔가 나름대로 열심히 생각해봤는데 어려웠다. ㅜㅜ 그래도 거의 시작은 근접한 것 같다. n*n 크기 자물쇠와 m*m 크기 열쇠라서 배열 크기를 n+2m으로 늘린 다음

중앙 부분에 자물쇠를 위치시키고

계속 돌리면서 맞는지 안맞는지 확인

 

그런데 맞는지 안맞는지를 도대체 어떻게 아나 했더니 이건 완전탐색이었다. 세상에 ㅜ

 

n>m이기 때문에 배열 크기도 그냥 3n으로 늘린단다. 이건 좀 좋은 팁인듯

 

 

그 다음 답지를 참고해 개선한 코드

 

def rotate(key):
    #90도 회전
    n = len(key)
    m = len(key[0])
    
    result = [[0]*n for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = key[i][j]
    return result

def check(new_lock):
    lock_length = len(new_lock)//3
    for i in range(lock_length, lock_length*2):
        for j in range(lock_length, lock_length*2):
            if new_lock[i][j] != 1:
                return False
    return True

def isopen(n, m, key, new_lock):
    #맞는지 안맞는지
    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) == True:
                return True

          for i in range(m):

              for j in range(m):
                  new_lock[x+i][y+j] -= key[i][j]
    
    return False

def solution(key, lock):
    n = len(lock)
    m = len(key)
    new_lock = [[0 for _ in range(n*3)] for _ in range(n*3)]
    
    #i = m-1
    #j = m-1
    #new_lock[i][j]
    
    for i in range(n):
        for j in range(n):
            if lock[i][j] == 1:
                new_lock[i+n][j+n]=1
    
    for _ in range(4):
        if isopen(n, m, key, new_lock):
            return True
        else:
            key = rotate(key)
    
    return False

 

그런데 답이 틀려서 확인해보니 인덴트가 틀려서 답이 다르게 나오는 것이었다

인덴트도 잘 확인해야겠다 앞으로..

또한 답이 아닐 경우에 자물쇠를 초기화해줘야한다.

 

답지를 확인해서 알아낸 최종 코드

 

def rotate(key):
    #90도 회전
    n = len(key)
    m = len(key[0])
    
    result = [[0]*n for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = key[i][j]
    return result

def check(new_lock):
    lock_length = len(new_lock)//3
    for i in range(lock_length, lock_length*2):
        for j in range(lock_length, lock_length*2):
            if new_lock[i][j] != 1:
                return False
    return True

def solution(key, lock):
    n = len(lock)
    m = len(key)
    new_lock = [[0 for _ in range(n*3)] for _ in range(n*3)]
    
    #i = m-1
    #j = m-1
    #new_lock[i][j]
    
    for i in range(n):
        for j in range(n):
            if lock[i][j] == 1:
                new_lock[i+n][j+n]=1
    
    for rotation in range(4):
        key = rotate(key)
        for x in range(n*3-m): #답지에는 2n까지 확인하는 것으로 되어있는데 나는 정확한 완전 탐색을 테스트해봤다.
            for y in range(n*3-m):
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] += key[i][j]
                
                if check(new_lock) == True:
                    return True
                
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] -= key[i][j]
    
    return False