[구현] 자물쇠와 열쇠

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

- 키와 자물쇠에 대한 배열이 주어질 때, 해당 키로 자물쇠를 풀 수 있는지를 묻는 문제

- 다양한 조건이 있어서 해당 조건들을 고려하기 위해 최소 3개의 키포인트가 들어간다

2. 접근 방식

- Rotate 90이면 총 4번이 도는 거고, 격자 수 만큼 이동을 하면 되니까 for문을 돌면서 다 체크하면 될 거 같다.

- 열쇠가 초과하는 부분이 존재할 수도 있는데,,,그러면 빈 공간을 만들기 해야한다.

- 30분 정도 지났을 때, 이전에 풀었던 기억이 나오면서 절대 풀지 못하는 부분을 깨달아 해설을 봤다.

3. 코드

# 시계방향 
def rotate_matrix_90_degree(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0]*n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = a[i][j] # (키포인트 1)
    return result

# 완전 탐색을 하면서 리스트 확인
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):
    length = len(lock) 
    bound = len(key)
        
    # 자물쇠 크기 변환
    tmp_list = [[0]*(3*len(lock)) for _ in range((3*len(lock)))] #(키포인트 2)
    for i in range(length):
        for j in range(length):
            tmp_list[i+length][j+length] = lock[i][j]
    result = False

    # 4가지 방향에 대해서 확인_해당 부분 코드 못 만듬 (계속 돌려주고 키를 넣고 뺴고)
    for rotation in range(4):
        key = rotate_matrix_90_degree(key)
        for x in range(length*2):
            for y in range(length*2):
                # 자물쇠 끼어넣기 # (키포인트 3, 자물쇠를 넣고 빼야 한다.)
                for i in range(bound):
                    for j in range(bound):
                        tmp_list[x+i][y+j] += key[i][j]
                if check(tmp_list) == True:
                    return True
                # 자물쇠 빼기
                for i in range(bound):
                    for j in range(bound):
                        tmp_list[x+i][y+j] -= key[i][j]        
    return False

4. 코멘트

- 구현 문제는 귀찮음을 감수해야 하는 것 같다. 왜냐하면 이중 for문을 넘어서 4중 for문까지 들어가기 때문이다.

- 그리고 해당 문제가 '구현' 문제라는 것을 판단할 수 있는 안목도 중요한 것 같다. 해당 문제가 어떤 문제인지 바로 판단해서 풀 수 있냐 없냐로도 시간을 많이 줄일 수 있을 것 같다는 생각이 든다.

- 해당 문제는 나중에 다시 풀어서 해결방법을 기억해둘 필요가 있는게 나중에 사용할 수 있는 기법이 많은 것 같다.

(리스트에 값을 넣어 비교하고, 값을 다시 뺴는 기법, 리스트에 padding을 넣는 기법, 행렬의 값을 돌리는 기법)