[프로그래머스] 자물쇠와 열쇠 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

---

'''

    Chapter 12. 좌물쇠와 열쇠

    접근법 1

        완전 탐색 : 열쇠를 채울 수 있는 모든 경우 탐색

       

        열쇠의 오른쪽 가장 아래 부분과 자물쇠의 왼쪽 가장 위 부분만 겹치는 경우에서

        열쇠의 왼쪽 가장 위 부분과 자물쇠의 오른쪽 가장 아래 부분이 겹치는 경우까지

        +

        열쇠 90도 (4번)

        -> indexError를 막기 위해 자물쇠의 상하좌우를 연장

        ex) 프로그래머스 예시

        lock = [[3,3,3,3,3,3,3],

                [3,3,3,3,3,3,3],

                [3,3,1,1,1,3,3],

                [3,3,1,1,0,3,3],

                [3,3,1,0,1,3,3],

                [3,3,3,3,3,3,3],

                [3,3,3,3,3,3,3]]

        lock[0][0] ~ lock[4][4]까지 확인

        열쇠의 돌기와 자물쇠의 홈이 만나는 경우의 수 세기

            홈이 다 채워지면 True

            열쇠의 돌기와 자물쇠의 돌기가 만나는 경우가 나타나면 False

'''

def solution(key, lock):
    M = len(key)
    N = len(lock)
    
    # 자물쇠 홈의 개수
    cnt = 0
    for i in range(N):
        for j in range(N):
            if lock[i][j] == 0:
                cnt += 1
    
    # 자물쇠 범위 연장
    lock = [[3]*(2*M+N-2)]*(M-1) + [[3]*(M-1) + i + [3]*(M-1) for i in lock] + [[3]*(2*M+N-2)]*(M-1)
    
    # 열쇠 넣어보기
    def check(r,c):
        # 열쇠의 돌기 부분과 자물쇠의 홈 부분이 일치 하는 곳 수 
        yes = 0
        for i in range(M):
            for j in range(M):
                # 열쇠의 돌기와 자물쇠의 돌기가 만나는 경우
                if key[i][j] + lock[r+i][c+j] == 2:
                    return 
                # 열쇠의 돌기와 자물쇠의 홈이 만나는 경우
                elif key[i][j] == 1 and lock[r+i][c+j] == 0:
                    yes += 1
        # 자물쇠의 모든 홈을 채웠는가?
        if yes == cnt:
            return True

    for _ in range(4):
        # 자물쇠를 시계 방향으로 90도 회전
        rotate_key = [[0]*M for _ in range(M)]
        for i in range(M):
            for j in range(M):
                rotate_key[i][j] = key[M-1-j][i]
        key = rotate_key
        
        # 열쇠 넣어보기
        for r in range(M+N-1):
            for c in range(M+N-1):
                # 확인 시작점 (r,c) == 열쇠의 왼쪽 상단
                # 열쇠 넣어보기
                if check(r,c):
                    return True
    return False

'''

테스트 1 〉 통과 (0.22ms, 10.3MB)

테스트 2 〉 통과 (0.04ms, 10.3MB)

테스트 3 〉 통과 (2.25ms, 10.1MB)

테스트 4 〉 통과 (0.07ms, 10.4MB)

테스트 5 〉 통과 (10.48ms, 10.2MB)

테스트 6 〉 통과 (2.41ms, 10.3MB)

테스트 7 〉 통과 (17.20ms, 10.3MB)

테스트 8 〉 통과 (11.77ms, 10.2MB)

테스트 9 〉 통과 (19.37ms, 10.4MB)

테스트 10 〉    통과 (63.63ms, 10.1MB)

테스트 11 〉    통과 (102.42ms, 10.2MB)

테스트 12 〉    통과 (0.03ms, 10.2MB)

테스트 13 〉    통과 (2.94ms, 10.4MB)

테스트 14 〉    통과 (0.29ms, 10.3MB)

테스트 15 〉    통과 (1.83ms, 10.3MB)

테스트 16 〉    통과 (8.09ms, 10.2MB)

테스트 17 〉    통과 (23.21ms, 10.3MB)

테스트 18 〉    통과 (3.69ms, 10.3MB)

테스트 19 〉    통과 (0.25ms, 10.3MB)

테스트 20 〉    통과 (24.29ms, 10.3MB)

테스트 21 〉    통과 (48.72ms, 10.2MB)

테스트 22 〉    통과 (8.94ms, 10.3MB)

테스트 23 〉    통과 (0.98ms, 10.3MB)

테스트 24 〉    통과 (1.80ms, 10.2MB)

테스트 25 〉    통과 (25.57ms, 10.3MB)

테스트 26 〉    통과 (65.47ms, 10.2MB)

테스트 27 〉    통과 (161.37ms, 10.4MB)

테스트 28 〉    통과 (9.99ms, 10.2MB)

테스트 29 〉    통과 (3.26ms, 10.3MB)

테스트 30 〉    통과 (16.78ms, 10.3MB)

테스트 31 〉    통과 (9.75ms, 10.3MB)

테스트 32 〉    통과 (40.14ms, 10.1MB)

테스트 33 〉    통과 (12.13ms, 10.1MB)

테스트 34 〉    통과 (0.86ms, 10.4MB)

테스트 35 〉    통과 (1.09ms, 10.2MB)

테스트 36 〉    통과 (1.29ms, 10.4MB)

테스트 37 〉    통과 (1.56ms, 10.2MB)

테스트 38 〉    통과 (0.18ms, 10.4MB)

'''