[프로그래머스] 자물쇠와 열쇠 - PYTHON

문제 보기

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

프로그래머스

 

풀이 & 코드

해당 문제를 풀다가 검색으로 들어오신 분들은 다들 공감하실 거 같다. 풀다가 화가 나는 문제는 오랜만이다...ㅎ 특별한 알고리즘이 있다기 보다는 그냥 노가다 같은 문제이다. 범위와 값이 좀 헷갈릴 뿐! 시간 소요도 다른 문제들에 비해 상당했다.

 

필자는 lock블록을 확장 시키고 key를 이동 및 회전시켜가며 결합해보는 방식으로 코드를 작성했다. lx, ly는 확장된 lock의 x, y 좌표이고 kx,ky는 키의 x,y좌표이다. 따라서 lx, ly를 움직여 주면서 kx, ky를 사용해 해당 좌표에서의 lock과 key값을 더해 주었다. 만일 더한 값이 1이라면 홈에 돌기가 올바르게 들어가거나 아무일도 일어나지 않은 자물쇠 부분을 의미한다. 2라면 자물쇠 부분에 돌기를 추가한 것이고, 0이라면 돌기가 들어가지 않은 홈을 의미한다.

 

전체적인 흐름을 나타내는 solution 함수이다. 해당 함수가 복잡해질 것으로 예상돼 전체적인 흐름을 제외한 기능적인 부분은 함수로 별도 작성했다.

def solution(key, lock):
    m = len(key)
    n = len(lock) + 2*(m-1)
    for _ in range(4):
        key = rotate(key)
        for lx in range(n-m+1):
            for ly in range(n-m+1):
                ext_lock = extend(lock, len(key)-1)
                for kx in range(m):
                    for ky in range(m):
                        ext_lock[ly+ky][lx+kx] += key[ky][kx]
                        
                if iscorrect(ext_lock, m-1):
                    return True
            
    return False

 

 

먼저 lock을 확장시키는 함수이다.  lst는 2차원 배열인 lock을 n에는 상하좌우로 확장시켜주고 싶은 길이인 len(key)-1 을 넣었다.

def extend(lst, n):
    lst = [[0]*n + row + [0]*n for row in lst]
    size = len(lst[0])
    return [[0]*size]*n + lst + [[0]*size]*n

 

 

다음으로 회전 관련된 코드이다. 필자는 시계방향으로 90도씩 회전되도록 코드를 작성했고 이를 solution에서 4번 반복에 모든 회전방향에서의 key를 만족시켰다.

def rotate(lst):
    return [[row[i] for row in lst[::-1]] for i in range(len(lst[0]))]

참고로 unzip을 사용하면 더 깔끔하게 회전 기능 함수를 작성할 수 있다. 단 2차원 배열이 리스트 안에 튜플 형태로 만들어 진다.

def rotate2(lst):
    return list(zip(*lst[::-1]))

 

 

마지막은 열쇠가 잘 끼어졌는 지 확인 하는 함수이다. 주석으로 작성된 것 처럼 확장된 lock안에서 원래 lock부분을 발췌하고, 채워지지 않은 구멍인 0이나 자물쇠 부분에 열쇠의 돌기가 들어간 2가 나오면 False를 리턴하게 작성하였다.

def iscorrect(lst, n):
	// 확장된 lock 안에서 원래 lock 부분을 발췌
    size = len(lst) - 2*n
    lock = [row[n:n+size] for row in lst[n:n+size]]
    
	// lock에 열쇠가 맞게 끼어졌는 지 확인
    for row in lock:
        if 0 in row or 2 in row:
            return False
        
    return True

 

 

 

 

전체 코드

def extend(lst, n):
    lst = [[0]*n + row + [0]*n for row in lst]
    size = len(lst[0])
    return [[0]*size]*n + lst + [[0]*size]*n

def rotate(lst):
    rot = [[row[i] for row in lst[::-1]] for i in range(len(lst[0]))]
    return rot
        
def iscorrect(lst, n):
    size = len(lst) - 2*n
    lock = [row[n:n+size] for row in lst[n:n+size]]
    
    for row in lock:
        if 0 in row or 2 in row:
            return False
        
    return True

    
def solution(key, lock):
    m = len(key)
    n = len(lock) + 2*(m-1)
    for _ in range(4):
        key = rotate(key)
        for lx in range(n-m+1):
            for ly in range(n-m+1):
                ext_lock = extend(lock, len(key)-1)
                for kx in range(m):
                    for ky in range(m):
                        ext_lock[ly+ky][lx+kx] += key[ky][kx]
                        
                if iscorrect(ext_lock, m-1):
                    return True
            
    return False