[프로그래머스,python] 2020 KAKAO BLIND RECRUITMENT 자물쇠와 열쇠

 

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

---

# 1. 회전하는 매커니즘 

# 2. 상하좌우로 가는 매커니즘 >> pop하고 0을 appendleft하거나 popleft하고 0을 append
# 3. ** lock의 0이 있는 패턴을 저장해 **
#      key에서 1이 있는 패턴이 위에서 구한 패턴과 같은지 봐. 없으면 회전시켜봐.
#      회전3번 해도 없으면 false를 리턴해.

# 4.  패턴이 존재한다면 두 이차원 배열끼리 포개서 합쳐.
#      만약 포개서 합칠때 2가 있다면 다시 회전해서 패턴을보고, 끝까지 없다면 다시 false를 리턴해.
#

def solution(key,lock):
    def rotated(key):  # 90도 회전하기
        row = len(key)  # row
        col = len(key[0])  # col

        result = [[0] * row for _ in range(col)]

        for i in range(row):
            for j in range(col):
                result[j][row - i - 1] = key[i][j]

        return result

    def find_pattern(key,lock,cnt):

        getpattern by lines

        if cnt>3:
            return False

        if key_pattern == lock_pattern:
            sum_cover(key,lock)
        else:
            cnt+=1
            find_pattern(rotated(key),lock)

    def sum_cover(key,lock):
        if is_two_exist:
            return False
        else:
            return True
    cnt=0
    return find_pattern(key,lock,cnt)

 

처음에 생각은 이랬으나, 1시간정도 고민해도 lock에서의 패턴을 받아 오는 법이 안떠올라서 다른 방법을 찾다가 맵을 크게 만들어서 하기로 했다..

 

  이런식으로 가운데에 lock을 두고 key의 너비만큼 8방향으로 붙여준뒤에 bfs로 쭉쭉 비교하고, 90도 회전하고 비교하고, 하는식으로 하기로 했다. 제한사항에서도 배열의 크기를 작게 제한한것을 보니 이렇게 풀라고 의도한것 같다.

1. 회전하기

def rotated(key):  # 90도 회전하기
    row = len(key)  # row
    col = len(key[0])  # col

    result = [[0] * row for _ in range(col)]

    for i in range(row):
        for j in range(col):
            result[j][row - i - 1] = key[i][j]

    return result

 

2. 탐색하면서 삽입하고, 판단하기

def search(key, lock,start_row,start_col):
    length = (2 * len(key)) + len(lock) # 확장시킬 한 변의 길이
    background = [[0] * length for _ in range(length)] # 확장시킨 2차원 배열

    for row in range(len(key)):
        for col in range(len(key[0])):
            background[row+start_row][col+start_col] = key[row][col]

    for row in range(len(key),len(key)+len(lock)):
        for col in range(len(key),len(key)+len(lock)):
            background[row][col] += lock[row-len(key)][col-len(key)]
            if background[row][col] != 1:
                return False

    return True

백그라운드라는 새로운 2차원 리스트를 만들어서 key값이 움직이는것을 백그라운드로 받아주고 계산을 해서 lock을 넣어줄 자리에 1이 하나라도 없다면 false, 아니라면 전부 1이되므로 true를 반환해주었다. 이부분이 잘 구현이 되지 않아서, 참고하였다.

 

3. 메인함수

def solution(key, lock):
    end = len(key) + len(lock)
    for k in range(4):
        for row in range(end):
            for col in range(end):
                start_row = row
                start_col = col
                if search(key, lock, start_row, start_col) == True:
                    return True
        key = rotated(key)

    return False

 

[0,0]~[len(key)+len(lock),len(key)+len(lock)] 까지 시작점을 바꾸면서 search하고, 270도 회전후에 마무리 했다.

 

 

def rotated(key):  # 90도 회전하기
    row = len(key)  # row
    col = len(key[0])  # col

    result = [[0] * row for _ in range(col)]

    for i in range(row):
        for j in range(col):
            result[j][row - i - 1] = key[i][j]

    return result


def search(key, lock, start_row, start_col):
    length = (2 * len(key)) + len(lock)  # 확장시킬 한 변의 길이
    background = [[0] * length for _ in range(length)]  # 확장시킨 2차원 배열
    end = len(key) + len(lock)

    for row in range(len(key)):
        for col in range(len(key[0])):
            background[row + start_row][col + start_col] = key[row][col]

    for row in range(len(key), end):
        for col in range(len(key), end):
            background[row][col] += lock[row - len(key)][col - len(key)]
            if background[row][col] != 1:
                return False

    return True


def solution(key, lock):
    end = len(key) + len(lock)
    for k in range(4):
        for row in range(end):
            for col in range(end):
                start_row = row
                start_col = col
                if search(key, lock, start_row, start_col) == True:
                    return True
        key = rotated(key)

    return False

 

 

참고자료

https://ysyblog.tistory.com/126