[구현] 자물쇠와 열쇠

1. 문제

풀어보기 (프로그래머스)

Key로 Lock을 풀수 있는 방법이 있는가?

가능한 방법 : 회전, 이동

0은 들어간부분, 1은 튀어나온 부분

 

2. 입력

# SET - 1
key	= [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
lock	= [[1, 1, 1], [1, 1, 0], [1, 0, 1]]

3. 출력

# SET - 1
result = True

4. 풀이

회전함수를 구현해야한다.

여기서 중요한 건, 회전한 키의 type이 Lock에서 가져온 홈 파인부분과 일치하지 않으면, False를 반환하게 된다.

이 점을 유의해서 회전함수를 구현하는 것이 필요

 

회전함수를 구현했으면, 이후에 어떻게 저 홈에 키를 끼워맞출 것인지, 생각해야 하는데

본인의 경우에는 Lock에서 홈이 패인 부분만 가져와서 Key에 이리저리 맞춰보기로 했다.

 

Lock의 값을 반전해서 값이 같아야 Key로 끼워맞출 수 있으므로, 값을 반전한 뒤, 

Key의 Length - 떼어온 부분의 길이 + 1만큼 탐색 (Row, Col 각각)

 

이렇게 하면 얼추 맞았다고 생각했는데 런타임 에러가 남

 

Lock이 전부 1일경우를 고려하지 않았기 때문...

이에 대한 예외처리를 넣으면 답을 맞출 수 있다.

 

5. 코드

# Python 회전함수 [(value, value), (value, value)] 리스트(튜플)
def rotate(key):
    return list(zip(*key[::-1]))

# Python 회전 (직접 구현) 리스트(리스트)
def rot90(square):
    len_row = len(square)
    len_col = len(square[0])
    temp = [[0 for _j in range(len_row)] for _i in range(len_col)]
    
    for i, row in enumerate(square):
        for j, value in enumerate(row):
            
            temp[j][len_row-i-1] = value
    return temp

def solution(key, lock):
	# Lock에서 파인부분을 가져옴
    min_i, max_i, min_j, max_j = len(lock), 0, len(lock), 0
    for i, row in enumerate(lock):
        for j, c in enumerate(row):
            if c == 0:
                min_i = min(i, min_i)
                max_i = max(i, max_i)
                min_j = min(j, min_j)
                max_j = max(j, max_j)
    part = []
    for row in lock[min_i:max_i+1]:
        part.append(row[min_j:max_j+1])
    
    # 자물쇠가 만약 전부 1이면, True 반환
    if not part:
        return True
        
    # 값 반전
    part = [[0 if c_p else 1 for c_p in p_row] for p_row in part]
    
    # 4번 회전하면서 일치하는 경우가 있는지 확인
    for _ in range(4):
        part = rotate(part)
        row_range = len(key)-len(part)+1
        col_range = len(key)-len(part[0])+1
        for i in range(row_range):
            for j in range(col_range):
                key_search = []
                for row in key[i:i+len(part)]:
                    key_search.append(tuple(row[j:j+len(part[0])]))
                if key_search == part:
                    return True

    return False