10_자물쇠와 열쇠

프로그래머스

 

문제를 읽고나서 처음에는 이렇게 생각했다.

자물쇠의 크기는 열쇠 크기 이상이므로 열쇠를 꽂을 수 있는 모든 경우의 수에 꽂아봐서 맞는 경우에는 True, 아니면 False를 리턴하자라고 생각했다.

문제 제한시간이 1초였고, 자물쇠와 열쇠의 크기는 20이하였다.

1초에 2,000만번 정도의 연산이 가능하므로 O(N^4) 이상도 가능한 수치여서 완전 탐색으로 풀 수 있는 문제이다.

---

첫 풀이

처음에는 lock에서 0인 부분은 key에서 1이여야하고, lock에서 1인 부분은 key에서 0이여야 한다고 생각했다.

그래서 key에서 lock에 집어 넣을 수 있는 모든 경우의 수에서 위 사항을 체크해서 모두 만족할 경우 true를 리턴하고, 하나라도 만족 못하면 false를 리턴하면 되겠다고 생각했다.

 

여기서 막혔던 점이 lock에는 key의 전체, 혹은 일부분만 들어갈 수 있는데 for문을 어떻게 작성해야 하나의 인덱스로 Key와 lock을 모두 돌면서 확인할 수 있을까라는 점이었다.

key가 lock에 일부분만 들어가는 경우, key가 lock에 모두 들어가는 경우를 나누어서 해줄까를 생각해봤지만, 식이 너무 복잡해졌고, 4중 for문을 넘어서 5중, 6중 for문까지 나와서 이 방법은 아니라고 생각했다.

 

 

두번째 풀이

lock보다 훨씬 큰 2차원 배열을 새로 만들어서 여기다가 기존 lock을 가운데에다가 넣고 key를 넣어보면서 비교하는 방법을 생각하긴 했었다.

다만 여기서도 key와 lock을 어떻게 하나의 인덱스로 돌면서 확인할 수 있을까? 라는 틀에 막혀서 진행하지 못했고, 결국 답을 봤다.

 

---

풀이

결국 lock보다 큰 2차원 배열을 만들어서 푸는 것은 맞았다.

하지만 key를 lock에 집어넣는 로직을 훨씬 더 쉽게 만들었다.

 

lock 배열을 커다란 2차원 배열의 중간에다가 넣고, key를 위에서부터 집어 넣으면서 lock에 key가 딱 맞는지 확인하면 된다!

 

문제에서 0은 홈부분, 1은 돌기부분을 나타내는데, 따라서 lock에 key의 값을 더한 뒤, 더한 결과를 확인했을 때, lock의 모든 값이 정확히 1이라면, 자물쇠의 홈 부분을 정확히 채운것이다!

 

그리고 한 번 확인할 때마다 key를 90도 돌리면서 확인하므로 한 번 확인할 때마다 총 4번을 확인한다.

 

풀이 코드

# Q_10_자물쇠와 열쇠

# 2차원 리스트 시계 방향 90도 회전
def roate_a_matrix_by_90_degree(arr):
    n = len(arr) # 행 길이
    m = len([arr[0]]) # 열 길이

    result = [[0] * n for _ in range(m)] # 결과 리스트

    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = arr[i][j]

    return result


# 자물쇠의 중간 부분이 모두 1인지 확인
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)

    # 자물쇠의 크기를 기존의 3배로 변환
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]

    # 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
    for i in range(n):
        for j in range(m):
            new_lock[n+i][m+j] = lock[i][j]

    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = roate_a_matrix_by_90_degree(key)
        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
                # 자물쇠에서 열쇠 다시 빼기
                else:
                    for i in range(m):
                        for j in range(m):
                            new_lock[x+i][y+j] -= key[i][j]

    
    return False

 

빡세게 하자..

 

 

 

 

---

2024.01.26

import copy

# key를 시계방향으로 회전시키는 함수
def rotate_right(arr):
    rotated_arr = [[0] * len(arr) for _ in range(len(arr))]
    for i in range(len(arr)):
        for j in range(len(arr)):
            rotated_arr[j][len(arr)-1-i] = arr[i][j]
            
    return rotated_arr


    
def solution(key, lock):
    n = len(lock)
    m = len(key)
    length = n + 2 * m - 2
    mapp = [[0] * length for _ in range(length)] 
    # 가로, 세로가 (n + 2*m - 2)인 전체 지도

    # map 가운데에 lock 위치
    for i in range(n):
        for j in range(n):
            mapp[m-1+i][m-1+j] = lock[i][j]
            
    # key 배치 시작
    check_mapp = copy.deepcopy(mapp) # 반복문을 돌면서 확인할 맵
    
    for i in range(len(mapp)-(m-1)):
        for j in range(len(mapp)-(m-1)):
            for _ in range(4):# 4번 회전
                key = rotate_right(key)
                
                # 자물쇠에 열쇠 넣기
                for k in range(m):
                    for l in range(m):
                        check_mapp[i+k][j+l] += key[k][l]
                    
                # 확인해야할 자물쇠
                check_lock = list(map(lambda x: x[m-1:m-1+n], check_mapp[m-1:m-1+n]))
                # print(check_lock)
                # 자물쇠의 모든 원소가 1이면 True 리턴
                if sum([row.count(1) for row in check_lock]) == n * n:
                    return True
                
                # 자물쇠의 모든 원소가 1이 아니라면, key를 다시 넣어서 확인해야 하므로 map 초기화
                check_mapp = copy.deepcopy(mapp)
    
    return False

 

노다가로 다시 풀었다.

이런 구현 문제는 많이 풀어봐야 늘 듯 하다.

계속 풀자..