[Programmers] 자물쇠와 열쇠 (Lv.3) 2024/3/31

문제 제목	정답률	난이도
자물쇠와 열쇠	40%	Lv.3

프로그래머스

 

문제요약

자물쇠의 홈과 열쇠의 돌기 부분이 모두 일치할 때, 자물쇠가 열린다.

조건 1) 열쇠는 회전+이동할 수 있다.

조건 2) 조건1 이후 열쇠의 돌기가 자물쇠의 돌기와 일치하면 안 된다.

 

 

풀이

Step1. 자물쇠의 홈과 열쇠의 돌기의 위치 찾기

• 최대 점과 최소 점을 구한 뒤 개수를 센다.
• y축 위의 양의 정수의 점의 개수를 센다.(x축 위의 양의 정수의 점의 개수는 세지 않는다)

Step2. 열쇠를 회전+이동시키며 자물쇠의 홈과 열쇠의 돌기가 일치하는지 확인

• 적어도 하나의 칸은 일치해야 한다. 이동범위  : #0~lock+key-1
• 열쇠의 돌기와 자물쇠의 돌기가 하나라도 일치하면 안된다.
• 열쇠의 돌기와 자물쇠의 홈이 모두 일치해야 한다.
• 오른쪽 90도 회전시 [x, y] -> [y, len(key)-1-x]

 

※※ 풀이는 모두 맞았는데, list는 삽입된 순서대로 보전이 안되는 것 같다. + heapq와 list와 유사한 시간복잡도를 지닌다.

def rotate(key_xy, key_size):
    answer=[]
    for xy in key_xy:
        answer.append([xy[1], key_size-1-xy[0]])
    return answer

def solution(key, lock):
    key_xy=[[row_idx, col_idx] for row_idx in range(len(key)) for col_idx in range(len(key)) if key[row_idx][col_idx]==1]
    lock_xy=[[row_idx, col_idx] for row_idx in range(len(lock)) for col_idx in range(len(lock)) if lock[row_idx][col_idx]==0]
    
    if len(lock_xy)==0:
        return True
    if len(key_xy)<len(lock_xy):
        return False

    for _ in range(0, 4):
        for row_idx in range(-(len(key)-1), len(lock), 1): #0~lock+key-1
            for col_idx in range(-(len(key)-1), len(lock), 1):
                now_lock_xy=lock_xy[:]
                now_key_xy=[]
                for xy in key_xy:
                    if (xy[0]+row_idx)>=0 and (xy[0]+row_idx)<len(lock) and (xy[1]+col_idx)>=0 and (xy[1]+col_idx)<len(lock):
                        now_key_xy.append([xy[0]+row_idx, xy[1]+col_idx])

                now_key_xy.sort()
                now_lock_xy.sort()
                
                while len(now_lock_xy)>0 and len(now_key_xy)>0:
                    key_element=now_key_xy[-1]
                    lock_element=now_lock_xy[-1]
                    if key_element==lock_element:
                        now_key_xy.pop()
                        now_lock_xy.pop()
                    else:
                        break
                if len(now_lock_xy)==0 and len(now_key_xy)==0:
                    print(_, row_idx, col_idx)
                    return True
        key_xy=rotate(key_xy, len(key))
    return False