자물쇠와 열쇠

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

프로그래머스

---

try1

문제를 보고 핵심은 회전, 이동, 비교 알고리즘일 것 같다는 생각이 듬

비교 알고리즘에서 자물쇠 홈들 간의 위치 관계를 이용해서 구할 것인가 아니면 열쇠가 이동하는 모든 경우의 수로 구할 것인가 고민하였음

전자의 경우 잘 되지않아 후자로 함

크게 나눠서 회전, 이동, 비교 알고리즘을 각각 짜고 마지막에 합침

 

※ 나의 코드

def solution(key, lock):
    answer = False

    # 자물쇠 홈 부분 추출
    hole = []
    for r, lo in enumerate(lock):
        if 0 in lo:
            for c, v in enumerate(lo):
                if v == 0:
                    hole += [(r, c)]

    # 열쇠를 자물쇠와 동일한 크기로 변경
    if len(key) < len(lock):
        for k in key:
            k += [0] * (len(lock) - len(key))
        key += [[0] * len(lock)] * (len(lock) - len(key))

    # 열쇠 회전
    angle = [0, 90, 180, 270]
    for an in angle:
        rotate = key.copy()
        for _ in range(int(an/90)):
            rotate = list(zip(*rotate[::-1]))

        # 열쇠 행 이동
        for rmove in range(-len(lock) + 1,len(lock),1):
            if rmove < 0:
                check = [[0] * len(rotate)] * abs(rmove) + rotate[:len(rotate) + rmove]
            if rmove >= 0:
                check = rotate[rmove:] + [[0] * len(rotate)] * rmove
            
            # 열쇠 열 이동
            copykey = check.copy()
            for cmove in range(-len(lock) + 1,len(lock),1):
                for id, k in enumerate(check):
                    if cmove < 0:
                        copykey[id] = list(k[abs(cmove):]) + [0] * abs(cmove)
                    if cmove >= 0:
                        copykey[id] = [0] * abs(cmove) + list(k[:len(rotate) - cmove])
                
                # 열쇠 돌기 부분 추출
                keyshape = []
                for r, ck in enumerate(copykey):
                    if 1 in ck:
                        for c, v in enumerate(ck):
                            if v == 1:
                                keyshape += [(r, c)]

                # 자물쇠 홈과 열쇠 돌기가 딱 맞는지 확인
                if hole == keyshape:
                    answer = True
                    # print(an, rmove, cmove)
                
                # 반복문 조기 종료
                if answer:
                    break
            if answer:
                break
        if answer:
            break

    return answer

문제풀이)

비교를 위한 자물쇠 홈 부분을 추출하여 hole에 (행인덱스, 열인덱스) 형태로 넣음

열쇠의 크기가 자물쇠의 크기보다 작을 때, 비교를 쉽게하기 위해 열쇠의 아래와 오른쪽에 0을 채워 자물쇠의 크기로 키워줌

열쇠가 이동하는 모든 경우의 수를 보기위해서 행방향 2m-1가지와 열방향 2m-1 가지를 for문으로 돌림(m:자물쇠크기)

열쇠가 이동하고나서 자물쇠 기준으로 비는 부분은 비교를 쉽게하기 위해 0으로 채움

회전과 이동을 모두 한 후 비교를 위한 열쇠 돌기 부분을 추출하여 keyshape에 (행인덱스, 열인덱스) 형태로 넣음

자물쇠 홈 hole과 열쇠 돌기 keyshape가 같다면 answer에 True를 줌

answer가 True라면 모든 반복문을 종료함

 

테스트 결과) - 총합 1175.66 ms

테스트 1 〉	통과 (0.47ms, 10.4MB)
테스트 2 〉	통과 (0.02ms, 10.3MB)
테스트 3 〉	통과 (5.46ms, 10.4MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (13.70ms, 10.3MB)
테스트 6 〉	통과 (41.98ms, 10.2MB)
테스트 7 〉	통과 (4.81ms, 10.3MB)
테스트 8 〉	통과 (25.98ms, 10.4MB)
테스트 9 〉	통과 (56.13ms, 10.2MB)
테스트 10 〉	통과 (118.40ms, 10.4MB)
테스트 11 〉	통과 (132.50ms, 10.4MB)
테스트 12 〉	통과 (0.02ms, 10.3MB)
테스트 13 〉	통과 (4.09ms, 10.2MB)
테스트 14 〉	통과 (1.50ms, 10.3MB)
테스트 15 〉	통과 (0.18ms, 10.2MB)
테스트 16 〉	통과 (14.61ms, 10.4MB)
테스트 17 〉	통과 (9.30ms, 10.3MB)
테스트 18 〉	통과 (21.00ms, 10.3MB)
테스트 19 〉	통과 (1.80ms, 10.2MB)
테스트 20 〉	통과 (82.94ms, 10.3MB)
테스트 21 〉	통과 (23.26ms, 10.2MB)
테스트 22 〉	통과 (12.53ms, 10.3MB)
테스트 23 〉	통과 (2.82ms, 10.2MB)
테스트 24 〉	통과 (2.14ms, 10.3MB)
테스트 25 〉	통과 (115.25ms, 10.3MB)
테스트 26 〉	통과 (101.19ms, 10.2MB)
테스트 27 〉	통과 (152.75ms, 10.4MB)
테스트 28 〉	통과 (9.98ms, 10.3MB)
테스트 29 〉	통과 (3.81ms, 10.3MB)
테스트 30 〉	통과 (13.82ms, 10.4MB)
테스트 31 〉	통과 (74.09ms, 10.3MB)
테스트 32 〉	통과 (104.03ms, 10.3MB)
테스트 33 〉	통과 (16.99ms, 10.3MB)
테스트 34 〉	통과 (0.42ms, 10.3MB)
테스트 35 〉	통과 (1.12ms, 10.4MB)
테스트 36 〉	통과 (2.33ms, 10.3MB)
테스트 37 〉	통과 (1.50ms, 10.3MB)
테스트 38 〉	통과 (2.72ms, 10.4MB)

---

try2

열쇠 돌기 부분을 먼저 추출하고 이동시키는 방법이 더 짧게 걸리지 않을까하여 시도함

 

※ 나의 코드

def solution(key, lock):
    answer = False
    m = len(lock)

    # 자물쇠 홈 부분 추출
    hole = []
    for r, lo in enumerate(lock):
        if 0 in lo:
            for c, v in enumerate(lo):
                if v == 0:
                    hole += [(r, c)]

    # 열쇠 회전
    angle = [0, 90, 180, 270]
    for an in angle:
        rotate = key.copy()
        for _ in range(int(an/90)):
            rotate = list(zip(*rotate[::-1]))

        # 열쇠 돌기 부분 추출
        keyshape = []
        for r, rot in enumerate(rotate):
            if 1 in rot:
                for c, v in enumerate(rot):
                    if v == 1:
                        keyshape += [(r, c)]

        # 열쇠 행 열 이동
        for rmove in range(-m + 1,m,1):        
            for cmove in range(-m + 1,m,1):
                copykey = []
                for ks in keyshape:
                    if (ks[0] + rmove >= 0 and ks[0] + rmove < m) and (ks[1] + cmove >= 0 and ks[1] + cmove < m):
                        copykey += [(ks[0] + rmove, ks[1] + cmove)]
                
                # 자물쇠 홈과 열쇠 돌기가 딱 맞는지 확인
                if hole == copykey:
                    answer = True
                
                # 반복문 조기 종료
                if answer:
                    break
            if answer:
                break
        if answer:
            break

    return answer

문제풀이)

비교를 위한 자물쇠 홈 부분을 추출하여 hole에 (행인덱스, 열인덱스) 형태로 넣음

회전을 한 후 비교를 위한 열쇠 돌기 부분을 추출하여 keyshape에 (행인덱스, 열인덱스) 형태로 넣음

열쇠가 이동하는 모든 경우의 수를 보기위해서 행방향 2m-1가지와 열방향 2m-1 가지를 for문으로 돌림(m:자물쇠크기)

열쇠가 이동하고나서 자물쇠 범위에 있는 돌기의 위치를 copykey에 (행인덱스, 열인덱스) 형태로 넣음

자물쇠 홈 hole과 열쇠 돌기 copykey가 같다면 answer에 True를 줌

answer가 True라면 모든 반복문을 종료함

 

테스트 결과) - 총합 782.4 ms

테스트 1 〉	통과 (0.12ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.4MB)
테스트 3 〉	통과 (5.38ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (13.00ms, 10.4MB)
테스트 6 〉	통과 (9.19ms, 10.4MB)
테스트 7 〉	통과 (9.08ms, 10.4MB)
테스트 8 〉	통과 (29.11ms, 10MB)
테스트 9 〉	통과 (45.09ms, 10.3MB)
테스트 10 〉	통과 (101.81ms, 10.2MB)
테스트 11 〉	통과 (126.75ms, 10.1MB)
테스트 12 〉	통과 (0.02ms, 10.2MB)
테스트 13 〉	통과 (2.83ms, 10.3MB)
테스트 14 〉	통과 (0.38ms, 10.3MB)
테스트 15 〉	통과 (1.61ms, 10.3MB)
테스트 16 〉	통과 (10.56ms, 10.2MB)
테스트 17 〉	통과 (0.70ms, 10.1MB)
테스트 18 〉	통과 (11.54ms, 10.4MB)
테스트 19 〉	통과 (0.26ms, 10.3MB)
테스트 20 〉	통과 (43.17ms, 10.3MB)
테스트 21 〉	통과 (4.32ms, 10.2MB)
테스트 22 〉	통과 (10.20ms, 10.3MB)
테스트 23 〉	통과 (1.25ms, 10.2MB)
테스트 24 〉	통과 (0.63ms, 10.4MB)
테스트 25 〉	통과 (44.57ms, 10MB)
테스트 26 〉	통과 (73.43ms, 10.2MB)
테스트 27 〉	통과 (113.27ms, 10.2MB)
테스트 28 〉	통과 (7.98ms, 10.3MB)
테스트 29 〉	통과 (1.38ms, 10.3MB)
테스트 30 〉	통과 (10.92ms, 10.3MB)
테스트 31 〉	통과 (23.35ms, 10.3MB)
테스트 32 〉	통과 (65.12ms, 10.2MB)
테스트 33 〉	통과 (11.99ms, 10.2MB)
테스트 34 〉	통과 (0.06ms, 10.1MB)
테스트 35 〉	통과 (0.77ms, 10.4MB)
테스트 36 〉	통과 (1.30ms, 10.3MB)
테스트 37 〉	통과 (0.87ms, 10.3MB)
테스트 38 〉	통과 (0.37ms, 10.2MB)