[이.취.코] [프로그래머스] Chap 12. 구현 - Q10. 자물쇠와 열쇠

@mildsalmon·2021-09-15 10:34

1. 자물쇠와 열쇠

난이도
- 중하
풀이 시간
- 40분
시간 제한
- 1초
메모리 제한
- 128 MB
출처
- 코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스 (programmers.co.kr)

A. 문제

위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안

a. 1차 시도 (실패 - 21.09.15)


def move(key, d_count):  
    d = [[0, len(key), 0, len(key)],  
         [0, len(key), len(key), 0],  
         [len(key), 0, len(key), 0],  
         [len(key), 0, 0, len(key)]]  
  
    new_key = [[0] * len(key) for i in range(len(key))]  
  
    for i in range(d[d_count][0], d[d_count][1]):  
        for j in range(d[d_count][2], d[d_count][3]):  
            if d_count % 2 == 0:  
                new_key[i][j] = key[i][j]  
            elif d_count % 2 == 1:  
                new_key[i][j] = key[j][i]  
    return new_key  
  
  
def solution(key, lock):  
    for l in range(4):  
        new_key = move(key, l)  
  
        for i in range(len(lock)):  
            for j in range(len(lock)):  
                # for k in range(len(key)):  
                if lock[i][j] == 0 and new_key[i][j] == 1:  
                    return True  
  
 return False

b. 2차 시도 (실패)


def move_key(key):  
    # 키 행렬을 회전  
  
 row = len(key)  
    column = len(key[0])  
    new_key = [[0] * column for i in range(row)]  
  
    for i in range(row):  
        for j in range(column):  
            new_key[i][j] = key[(row - j) - 1][i]  
    # print(*new_key, sep='\n')  
    # print() return new_key  
  
  
def solution(key, lock):  
    row = len(lock)  
    column = len(lock[0])  
    extend_lock = [[0] * column * 3 for i in range(row * 3)]  
  
    for i in range(row):  
        for j in range(column):  
            extend_lock[row + i][column + j] = lock[i][j]  
  
    for m in range(4):  
        # temp_extend_lock = [i[:] for i in extend_lock]  
        for i in range(row*2):  
            for j in range(column*2):  
                count = 0  
                sample_key = [i[:] for i in key]  
                for k in range(len(key)):  
                    for l in range(len(key)):  
                        sample_key[k][l] += extend_lock[k+i][l+j]  
                for k in range(len(key)):  
                    for l in range(len(key)):  
                        if sample_key[k][l] == 1:  
                            count += 1  
                if count == 9:  
                    return True  
                print(*sample_key, sep='\n')  
                print()  
        key = move_key(key)  
  
    return False

c. 3차 시도 (성공)


def transform(key):
    key_len = len(key)
    temp = [[0] * key_len for i in range(key_len)]
    for i in range(key_len):
        for j in range(key_len):
            temp[i][j] = key[key_len - j - 1][i]

    return temp

def solution(key, lock):
    lock_len = len(lock)
    key_len = len(key)

    big_lock = [[0]*3*lock_len for i in range(3*lock_len)]

    # print(*big_lock, sep='\n')

    for i in range(lock_len, 2*lock_len):
        for j in range(lock_len, 2*lock_len):
            big_lock[i][j] = lock[i-lock_len][j-lock_len]

    # print(*big_lock, sep='\n')

    for _ in range(4):
        for i in range(len(big_lock)-key_len):
            for j in range(len(big_lock)-key_len):
                # 자물쇠에 열쇠 넣음
                for k_i in range(key_len):
                    for k_j in range(key_len):
                        big_lock[i+k_i][j+k_j] += key[k_i][k_j]

                # 올바른 키인지 확인
                count = 0
                for c_i in range(lock_len, 2*lock_len):
                    for c_j in range(lock_len, 2*lock_len):
                        if big_lock[c_i][c_j] == 1:
                            count += 1
                if count == (lock_len * lock_len):
                    return True
                # print(*big_lock, sep='\n')
                # print()
                # 올바른 키가 아니기 때문에 좌물쇠에서 열쇠 뺌
                for k_i in range(key_len):
                    for k_j in range(key_len):
                        big_lock[i+k_i][j+k_j] -= key[k_i][k_j]
        key = transform(key)
        # print(*key, sep='\n')
        # print()
    return False

d. 4차 시도 (key의 transpose를 변형함)


# 자물쇠와 열쇠

def transpose_key(key):
    new_key = []
    for k in zip(*key):
        new_key.append(k)
    new_key.reverse()
    return new_key


def check_lock(big_lock, lock_len):
    for x in range(lock_len, 2 * lock_len):
        for y in range(lock_len, 2 * lock_len):
            if big_lock[x][y] != 1:
                return False
    return True


def solution(key, lock):
    key_len = len(key)
    lock_len = len(lock)

    big_lock = [[0] * lock_len * 3 for i in range(lock_len * 3)]

    for i in range(lock_len, 2 * lock_len):
        for j in range(lock_len, 2 * lock_len):
            big_lock[i][j] = lock[i - lock_len][j - lock_len]

    # print(*big_lock,sep='\n')

    for _ in range(4):
        key = transpose_key(key)

        # print(*key, sep='\n')
        # print()

        for i in range(2 * lock_len):
            for j in range(2 * lock_len):
                for x in range(key_len):
                    for y in range(key_len):
                        big_lock[i + x][j + y] += key[x][y]

                if check_lock(big_lock, lock_len):
                    return True

                for x in range(key_len):
                    for y in range(key_len):
                        big_lock[i + x][j + y] -= key[x][y]
                # print(*big_lock,sep='\n')
    return False

e. 회고

내 풀이

자물쇠를 왼쪽으로 90º 돌려야한다. -> 이것을 4번 반복해서 전 방향에 다 대입해본다.
자물쇠가 0인 부분에 키가 1이라면 true를 반환한다
- 이렇게 아주 단순하게 풀어서 틀렸다.

반성

lock 리스트를 확장하는 것에 대해 고려하지 못했다.

결론

틀렸다. 이해하는 것조차 오래걸렸다.
그래도 완전히 이해한 것 같다. 이는 반복 코딩을 통해 더 확실히 각인될 것 같다.
구현 중간중간에 자꾸 내가 만든 것을 print로 찍어봐야한다. 안그러면 어디서 에러가 발생하는지 처음부터확인해야 한다.

C. 문제 해설

이해한 내용을 바탕으로 작성했습니다.

자물쇠의 행렬 변환(90º 돌리는 행위)을 구현해야 한다.
key의 크기(M)은 항상 lock의 크기(N)이하라고 한다.
- lock의 크기를 3배 키운다.
- 입력으로 주어진 lock은 중앙에 배치한다.
키를 3배 키운 lock의 모든 자리에 대입한다.
만약 중앙에 위치한 lock이 모두 1이면 잠금이 해제된다.
- 그렇지 않으면 3배 키운 lock에 대입한 키를 다시 뺀다.