[Programmers/프로그래머스] 2020 KAKAO BLIND RECRUITMENT [코딩테스트]

1. [Lv. 2] 문자열 압축
2. [Lv. 2] 괄호 변환
3. [Lv. 3] 자물쇠와 열쇠
4. [Lv. 4] 가사 검색
5. [Lv. 3] 기둥과 보 설치
6. [Lv. 3] 외벽 점검
7. [Lv. 3] 블록 이동하기

📌 문제

📝 제한사항

💻 입출력 예

📖 입출력 예에 대한 설명

📌 풀이

# 시계방향 90도 회전
def rotate(key):
    m = len(key)
    rotated_key = [[0] * m for _ in range(m)]               # 회전 결과를 저장할 2차원 리스트
    for row in range(m):                                    # 열쇠의 각 행
        for col in range(m):                                # 열쇠의 각 열
            rotated_key[row][col] = key[m - 1 - col][row]   # 좌표를 이용한 2차원 리스트 회전
    return rotated_key

# 확장된 자물쇠의 중앙부 확인
def check(lock):
    n = len(lock) // 3                  # 확장된 자물쇠이므로 n // 3
    for row in range(n, n * 2):         # 자물쇠 중앙에 해당하는 각 행 
        for col in range(n, n * 2):     # 자물쇠 중앙에 해당하는 각 열
            if lock[row][col] != 1:     # 남아있는 홈이 있거나, 겹치는 돌기가 있다면
                return False            # return False
    return True

def solution(key, lock):
    n, m = len(lock), len(key)
    extended_lock = [[0] * (n * 3) for _ in range(n * 3)]       # 3배 크기 자물쇠
    for row in range(n):                                        # 자물쇠의 각 행
        for col in range(n):                                    # 자물쇠의 각 열
            extended_lock[row + n][col + n] = lock[row][col]    # 중앙에 해당하는 행, 열에 자물쇠 붙이기

    for _ in range(4):                      # 90, 180, 270, 360 4회 회전하며 확인
        key = rotate(key)                   # 자물쇠 회전
        for row in range(1, n * 2):         # 열쇠와 자물쇠가 겹치는 행 범위에서 이동하며 확인
            for col in range(1, n * 2):     # 열쇠와 자물쇠가 겹치는 열 범위에서 이동하며 확인
            
                # 열쇠를 일단 꽂아보고
                for i in range(m):          # 열쇠의 각 행 m
                    for j in range(m):      # 열쇠의 각 열 m
                        extended_lock[row + i][col + j] += key[i][j]
                
                # 자물쇠가 열리면 return True
                if check(extended_lock):
                    return True
                
                # 자물쇠가 열리지 않으면 원래상태로 복구
                for i in range(m):          # 열쇠의 각 행 m
                    for j in range(m):      # 열쇠의 각 열 m
                        extended_lock[row + i][col + j] -= key[i][j]
    
    return False	# 열 수 있는 방법이 없다면 return False

1. 자물쇠 영역을 벗어난 부분까지 확인하기 위해, 자물쇠의 주변으로 자물쇠를 3배 크기로 확장.
(M은 항상 N이하 이므로, 인덱스 오류 없음)
2. 좌표를 이용한 배열회전:
	new_row = n - 1 - old_col
    new_col = old_row