[이코테-구현] 실전 - 10. 자물쇠와 열쇠

[문제]

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

코딩테스트 연습 - 자물쇠와 열쇠

 

---

 

[책 풀이]

🔎 아이디어

• 열쇠를 회전하고 움직여서 자물쇠와 정확히 맞물리는지 완전 탐색한다.
• 열쇠가 회전하는  모든 경우의 수: 90도, 180도, 270도, 360도(제자리)를 고려한다.
• 열쇠가 자물쇠 위를 이동하는 모든 경우 수: 열쇠의 botton-right 모서리가 자물쇠의 top-left 모서리와 맞닿을 때 부터 ~ 열쇠의 top-left 모서리가 자물쇠의 botton-right 모서리와 맞닿을 때까지 열쇠를 sliding 한다.
• 즉 정사각형 자물쇠의 한 변의 길이가 n이라고 할 때, 새로운 자물쇠의 변의 길이가 3×n이 되도록 자물쇠의 위 아래 양 옆을  0의 값으로 padding 한다. (새로운 자물쇠의 가운데는 자물쇠의 값으로 채워져 있고, 나머지 위 아래 양 옆 값은 0 이다.)
• 이 padding된 새로운 자물쇠에 열쇠를 sliding하면서 맞물리는지 확인하면 된다.
• 열쇠의 값과 새로운 자물쇠의 값을 더해서, 새로운 자물쇠에서 가운데 영역의 값이 모두 1이면 자물쇠와 열쇠가 정확히 맞물리는 것이다.

 

🔎 코드

def rotate90(key):
  # 90도 회전하면 행 열 수가 바뀜
  new_row = len(key[0])
  new_col = len(key)
  
  rotated_key = [new_col*[0] for _ in range(new_row)]

  for i in range(new_row):
    for j in range(new_col):
      rotated_key[j][new_col-i-1] = key[i][j]
      
  return rotated_key

def check_sum(n, new_lock):
  for i in range(n):
    for j in range(n):
      if new_lock[n+i][n+j] != 1:
        return False
        
  return True

def solution(key, lock):
  m = len(key)
  n = len(lock)

  # 열쇠가 자물쇠 위에서 이동하기 위해, lock을 padding한 new_lock 만들기
  new_lock = [(n*3)*[0] for _ in range(n*3)]

  # new_lock 가운데에 lock 값 넣기
  for i in range(n):
    for j in range(n):
      new_lock[n+i][n+j] = lock[i][j]

  # 4개의 회전에 대해서 모두 고려
  for _ in range(4):
    key = rotate90(key)
    # key를 이동하면서 new_lock 자물쇠에 끼워보기
    for x in range(n*2):
      for y in range(n*2):
        
        # key 와 lock 더하기
        for i in range(m):
          for j in range(m):
            new_lock[x+i][y+j] += key[i][j]
        
        # key가 new_lock에 끼워지는지 확인 == new_lock의 중앙값들(원래 lock 부분)이 모두 1이다.
        if check_sum(n, new_lock) == True:
          return True

        # key가 자물쇠에 딱 맞지 않았으므로 자물쇠에서 key 다시 빼기
        for i in range(m):
          for j in range(m):
            new_lock[x+i][y+j] -= key[i][j]

  # 모든 경우의 수를 다 고려했음에도(완전 탐색) key로 자물쇠를 열 수 없음
  return False

 

---

 

[느낀점]

열쇠가 자물쇠 위를 이동하는 모든 경우의 수를 고려하기 위해서 sliding window 개념을 떠올려야 했다.

 

---

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬 

* 포스팅에 책의 내용과 개인적인 해석이 같이 포함됩니다.