[프로그래머스/Lv.3] - 자물쇠와 열쇠

ZenTechie·2023년 7월 10일

programmers ps

PS

목록 보기

32/53

[자물쇠와 열쇠 문제링크]

아이디어

문제를 읽어보면 빡구현 문제임을 알 수 있다.

처리해야 할 조건을 다음과 같이 생각해봤다.

열쇠의 특정 영역이 자물쇠의 영역 안에 일부만 위치할 수 있다: 어떻게 일부 영역만 확인할 수 있게 할 것인가?
열쇠는 90도 회전할 수 있다
자물쇠 채우고 다음 비교를 위해 되돌리기
자물쇠의 모든 홈이 채워졌는지 확인하기

이를 코드로 구현하면 된다.

코드

# 열쇠 회전
def rotate_key(key):
    return list(zip(*key[::-1]))

# 열쇠로 자물쇠 채우기
def fill_in(x, y, m, new_lock, key):
    for i in range(m):
        for j in range(m):
            new_lock[x + i][y + j] += key[i][j]
            
# 채운 자물쇠 되돌리기
def fill_out(x, y, m, new_lock, key):
    for i in range(m):
        for j in range(m):
            new_lock[x + i][y + j] -= key[i][j]

# 모든 홈을 채웠는지 확인
def check_lock(new_lock, n, m):
    for i in range(n):
        for j in range(n):
            if new_lock[m + i][m + j] != 1:
                return False
            
    return True

def solution(key, lock):
    n, m = len(lock), len(key)
    
    
    # 새로운 자물쇠
    new_lock = [[0] * (2 * m + n) for _ in range(2 * m + n)]
    
    # 새로운 자물쇠 만들기
    for i in range(n):
        for j in range(n):
            new_lock[m + i][m + j] = lock[i][j]
    
    rotated_key = key # 회전한 열쇠 담는 변수
    for _ in range(4):
        rotated_key = rotate_key(rotated_key) # 열쇠 회전 수행
        for i in range(1, m + n):
            for j in range(1, m + n):
                fill_in(i, j, m, new_lock, rotated_key) # 채워보자
                
                if check_lock(new_lock, n, m): # 확인하자
                    return True
                
                fill_out(i, j, m, new_lock, rotated_key) # 되돌리자
                
    return False

풀이

먼저, 자물쇠를 채우기 전에 열쇠의 특정 영역이 자물쇠의 영역 안에 일부만 위치할 수 있다를 해결해야 한다.

아래와 같이 체크 표시된 영역만 열쇠로 채우고 싶다.

열쇠는 자물쇠의 바깥 영역을 돌아다닐 수 있고, 이를 인덱스로만 처리하고자 하면 어떻게 인덱스를 설정하고 비교해야 하는지 머리가 어지럽다.

이는 단순하게 자물쇠의 영역을 넓혀서 해결할 수 있다.

즉, 자물쇠의 영역을 열쇠의 크기만큼 넓히면 된다.(자물쇠의 바깥 영역 크기 = 열쇠의 크기)

열쇠의 크기 M = 3, 자물쇠의 크기 N = 4라고 가정하고, 영역을 넓히면 아래와 같다.

초록색이 넓혀진 바깥 영역을 의미하고, 검은색은 기존의 자물쇠의 영역을 의미한다.
바뀐 영역의 가로와 세로의 크기는, 다음과 같다.

가로: 10
세로: 10

즉, 가로, 세로는 n + 2*m 이다.

 # 새로운 자물쇠
new_lock = [[0] * (2 * m + n) for _ in range(2 * m + n)]
    
# 새로운 자물쇠 만들기
for i in range(n):
	for j in range(n):
	new_lock[m + i][m + j] = lock[i][j]

열쇠의 회전은 어떻게 처리할까?
key = [[0, 0, 1], [1, 1, 0], [1, 0, 0]]라고 가정하자.

직관적인 방법은 아래 코드와 같다.

m = len(key)
new_key = [[0] * m for _ in range(m)]

for i in range(m):
	for j in range(m):
		new_key[i][j] = key[m - 1 - j][i]

다른 방법으로는 아래 코드가 있다.(✅ 다른 사람 코드 참고)

list(zip(*key[::-1]))

이게 어떤 의미일까?

회전 후 key(오른쪽)을 살펴보면 회전되기 전 key(왼쪽)의 첫번째 열이 첫번째 행으로 변한것이 보인다. 나머지도 보면, 2번째 열이 2번째 행으로 그리고 3번째 열이 3번째 행으로 변했다.
(✅ 열이 행으로 → 세로였던 것이 가로로 눕혀졌다)

즉, 기존의 열을 행으로 변환한 것이다.
그러나 여기서 유의해야 할 점은 기존의 열의 맨 밑에 있던 값이 행의 맨 첫번째 값으로 올라왔다.

그러므로 기존의 key를 역순으로 다시 정렬한 뒤에, 각 열을 list로 변환해야 한다.
(역순 정렬을 하지 않으면, 첫번째 행은 [0, 0, 1]이 된다.)