[프로그래머스/python] 자물쇠와 열쇠

알고리즘 자물쇠와 열쇠

자물쇠와 열쇠

2020 KAKAO BLIND RECRUITMENT

​

문제

프로그래머스

​

풀이

key의 돌기 부분을 lock 홈에 하나 씩 맞춰보고 맞지 않다면 90도 회전하면서 풀었습니다.

​

key의 돌기를 따로 배열에 빼놓고 lock 홈을 따로 배열로 빼놨습니다.

key의 돌기 중 한 개를 선택해서 lock 홈에 맞춰봅니다.

여기서 맞춰볼 때 key 돌기 배열 안의 요소는 전부 이동합니다. ( 돌기와 홈의 거리 만큼!)

맞춰볼 때 lock의 범위를 넘어가는 key의 돌기는 제외했습니다.

딱 맞는다면 lock과 key는 같습니다.

만약 같지 않다면, 90도 회전을 하며 이를 반복합니다.

​

풀이코드

def rotate90(li, length):
    rotated_li=[]
    for i in li:
        x,y = i
        rotated_li.append((y,length-1- x))
    return rotated_li

def setting_distance(li, x, y, length):
    set_distance = set([])
    for i in li:
        key_x, key_y = i
        if 0<=key_x+x<length and 0<=key_y+y<length:
            set_distance.add((key_x+x,key_y+y))
    # print(set_distance)
    return set_distance

def solution(key, lock):
    key_legth = len(key)
    lock_length = len(lock)
    key_postion = []
    lock_position = []
    for x in range(key_legth):
        for y in range(key_legth):
            if key[x][y]==1:
                key_postion.append((x,y))
    for x in range(lock_length):
        for y in range(lock_length):
            if lock[x][y]==0:
                lock_position.append((x,y))   

    set_lock = set(lock_position)
    if set_lock:
        pass
    else:
        return True
    for lock_pos in lock_position:
        lock_x, lock_y = lock_pos
        for i in range(4):
            key_postion = rotate90(key_postion, key_legth)
            for key_pos in key_postion:
                key_x, key_y = key_pos
                x_distance = lock_x - key_x
                y_distance = lock_y - key_y
                set_key = setting_distance(key_postion, x_distance,y_distance,lock_length)
                if (set_key == set_lock):
                    return True
    return False
    
    

​

가장 인기 많은 코드

def solution(key, lock):
    N = len(lock)
    v, vac = vacant(lock)
    if not vac: return True
    vac = vac[0]
    find = False
    for key in rotate(key):
        for i in range(len(key)):
            cnt = 0
            rr, cc = vac[0]-key[i][0], vac[1]-key[i][1]
            print(rr, cc)
            for j in range(i, len(key)):
                r, c = key[j]
                r, c = r+rr, c+cc
                if not (0 <= r < N and 0 <= c < N): continue
                if lock[r][c] == 1: break
                cnt += 1
            if cnt == v:
                find = True
                break
        if find: break
    if find: return True
    return False


def vacant(lock):
    N = len(lock)
    vac = []
    v = 0
    for r in range(N):
        for c in range(N):
            if lock[r][c] == 0:
                vac.append((r, c))
                v += 1
    return v, vac


def rotate(key):
    M = len(key)
    key1 = [(r, c) for r in range(M) for c in range(M) if key[r][c] == 1]
    key2 = [(M-r-1, c) for c, r in key1]
    key3 = [(r, M-c-1) for c, r in key1]
    key4 = [(M-r-1, M-c-1) for r, c in key1]

    key1 = quick_sort(key1)
    key2 = quick_sort(key2)
    key3 = quick_sort(key3)
    key4 = quick_sort(key4)
    print(key1, key2, key3, key4)

    return key1, key2, key3, key4


def quick_sort(arr):
    if not arr: return []
    pivot = arr[len(arr)//2]
    lesser, equal, greater = [], [pivot], []

    for pos in arr:
        if pos[0] < pivot[0]:
            lesser.append(pos)
        elif pos[0] > pivot[0]:
            greater.append(pos)
        else:
            if pos[1] < pivot[1]:
                lesser.append(pos)
            elif pos[1] > pivot[1]:
                greater.append(pos)

    return quick_sort(lesser) + equal + quick_sort(greater)