기출 5일차 | 자물쇠와 열쇠

Journey log·2021년 6월 1일

[이코테] 알고리즘 공부

목록 보기

13/21

📍 이것이 코딩테스트다(나동빈) - part3.알고리즘 유형별 기출문제 를 풀고 기록했습니다.

1. 자물쇠와 열쇠

문제 링크
https://programmers.co.kr/learn/courses/30/lessons/60059?language=python3

1.1 내 답안

생각해본 방법들
1. key의 홈 좌표 중 하나를 특정 규칙으로 이동시켜 lock의 한 홈에 맞추고 동일한 규칙으로 나머지 홈들도 맞추기. -> 경우의수 어떻게 고려해야할지 모르겠음
2. key를 상,하,좌,우, 90도회전하는 함수를 만들어서 lock과 대조하려했음. 최대 경우의 수는 4(회전)x2(n-1)C(n-1) -> 그런데 모든 경우의 수 고려하는 방법을 생각해내지 못함
3. lock에서 홈이 있는 박스(lock[min_row][min_col]와 lock[max_row][max_col]으로 만들어지는)를 구하고 key를 차례대로 스캔한다. -> 테스트케이스는 돌아가지만 정확성 36점

# 3번 방법
def solution(key, lock):
    answer = False
    
    # lock에서 홈(0)이 있는 반경을 찾음
    # 그리고 그걸 회전시키면서 key를 탐색함
    
    # lock에서 홈(0)이 있는 반경을 찾음
    # 반경은 [min_row, min_col]과 [max_row, max_col]이 생성하는 직사각형
    max_row, max_col = 0, 0
    min_row, min_col = len(lock), len(lock)
    for row in range(len(lock)):
        for col in range(len(lock)):
            if lock[row][col] == 0:
                max_row, max_col = max(row, max_row), max(col, max_col)
                min_row, min_col = min(row, min_row), min(col, min_col)
    check = [a[min_col:max_col+1] for a in lock]
    check = check[min_row:max_row+1] # 홈이 있는 박스. 
    
    # 90도 회전 함수
    def rotate90(box):
        array = [[] for _ in range(len(box[0]))]
        for numbers in box:
            for i in range(len(numbers)):
                a = []
                a.append(numbers[i])
                array[i] = a + array[i]
        return array

    
    # 회전시키면서 key와 대조
    rotate = 0 # 회전 수
    while rotate <= 3:
        vertical = len(key)-len(check)+1 # 수직으로 이동 횟수
        horizontal = len(key)-len(check[0])+1 #수평으로 이동 횟수
        for i in range(vertical):
            for j in range(horizontal):
                part = [a[j:j+len(check[0])] for a in key][i:i+len(check)]
                if check == part:
                    answer=True
                    break
        check = rotate90(check)
        rotate += 1
    
    
    return answer

1.2 책 답안

자물쇠와 열쇠의 크기는 20x20보다 작다. 모든 원소에 접근하기 위해 최대 400개의 연산이 필요.
- 이동 횟수를 세야하는 줄 알았는데 원소에 접근하는 횟수로 세네?
파이썬의 경우 일반적인 코딩테스트 채점 환경에서 1초에 2,000만에서 1억정도의 연산 처리가능. 그래서 열쇠를 이동하거나 회전하면서 자물쇠에 끼워보는 작업을 전부 시도해봐도 됨
완전탐색을 수월하게 하기 위해 자물쇠 리스트의 크기를 3배 이상으로 변경하면 계산이 수월해진다. 열쇠크기만큼 한칸씩 이동하며 열쇠(행렬)+자물쇠(행렬)을 구함
0은 홈부분, 1은 돌기부분이니까 열쇠+자물쇠의 원소가 모두 1이면 열 수 있음.
rotate_a_matrix_by_90_degree() 함수를 구현하는데, 파이썬에서 2차원 리스트를 다룰 때 가끔 쓰니까 팀노트에 적어두고 필요할 때 사용하면 좋다..


# 2차원 리스트 90도 회전
def rotate_a_matrix_by_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] 
    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배로 변환 (0으로 먼저 만들고 가운데 채우기)
    new_lock = [[0]*(n*3) for _ in range(n*3)]  
    
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j] 
            # range는 몇개인지만 쓰고 new_lock[i+n][j+n]으로 설정하는게 더 편하네
    

    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
        for x in range(n*2): # n*3 아님
            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
                # 자물쇠에서 다시 열쇠 빼기
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] -= key[i][j]
    return False