https://school.programmers.co.kr/learn/courses/30/lessons/60059
카카오 2020 블라인드 3번 문제이다
얼마남지 않은 카카오 하반기 코딩테스트를 대비하기 위해 문제를 풀어봤다.
접근방식을 몰라서 카카오 해설을 참고하였다!
https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/
처음에 작성한 코드
접근 방식
- 회전을 하고 키를 이동해서 lock값과 key값을 더했을 때 1이 나와야 한다.
-> 시계 방향으로 회전 함수를 만들어서 90도로 돌려줬다.
def rotate(key):
n = len(key)
rotate_key = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotate_key[j][n-i-1] = key[i][j]
return rotate_key- 키를 움직이면서 lock의 빈 값을 채워줘야한다. 따라서 lock의 범위를 팽창시키고, key값을 더하여 원래 있던 lock의 공간이 1로 채워져있는지 확인하면 된다.
다음과 같이 원래 lock의 길이 + 상하좌우 Key를 움직이면서 확인하기 위한 Key만큼의 길이를 상하좌우로 팽창시켜줘야 한다
board = [[0] * (N + 2*M) for _ in range(N + 2*M)]
for i in range(N):
for j in range(N):
board[M+i][M+j] = lock[i][j]Board값을 팽창하는 부분에서 접근이 처음에 막혔다.
처음에 범위를 단순히 lock의 3배로 지정해줬었는데 기존에 안내된 key와 lock의 길이를 각각 M, N이라고 할 때 N <= M 이라고 주어졌기 때문에 M이 3이고 N이 20인 경우 런타임 에러가 발생한다.
- Key에 대해 0 ~ N+2M 만큼 보드를 순회하면서 lock과 더하여 해당 조건을 만족하는지 확인해야 한다.
순회를 할 때 범위를 잘 정해야 한다. 만약 0,0을 조회한다면 겹치는 부분이 하나도 없기 때문에 반드시 초기값과 다른 차이가 없다.
마찬가지로 (N+M, N+M)에서 조회를 했을 때도 겹치는 부분이 하나도 없다.
이를 고려해서 범위를 (1, N+M)으로 제한을 두고 해야한다.
처음에 작성한 코드
def rotate(key):
n = len(key)
rotate_key = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotate_key[j][n-i-1] = key[i][j]
return rotate_key
def compare(key, lock, n, m):
for w in range(3*n - m):
for h in range(3*n - m):
flag = True
for i in range(m):
for j in range(m):
if lock[i][j] + key[w+i][h+j] != 1:
flag = False
break
if flag:
return True
return False
def solution(key, lock):
n = len(key)
m = len(lock)
expaneded_key = [[0] * (3 * n) for _ in range(n * 3)]
#
for i in range(m):
for j in range(m):
expaneded_key[m+i][m+j] = key[i][j]
for i in range(4):
expaneded_key = rotate(expaneded_key)
if compare(expaneded_key, lock, n, m):
return True
return False
처음에 접근할 때 단순히 key값을 팽창하고, 돌려가면서 조회했다. 이 경우에 런타임에러가 발생된다. 이를 통해 배열의 인덱스를 접근할 때 잘못되었다는 것을 알 수 있었다.
수정한 코드
def compare(board,key,x,y,M, N):
answer = True
# x,y는 key를 더할 시작 좌표
# M은 키의 길이로 board에 키 전체값을 더해야한다.
for i in range(M):
for j in range(M):
board[x + i][y + j] += key[i][j]
for i in range(N):
if not answer: break
for j in range(N):
if board[i+M][j+M] != 1:
answer = False
break
# 더해진 board에 다시 key 빼기
for i in range(M):
for j in range(M):
board[x+i][y+j] -= key[i][j]
return answer
def solution(key, lock):
N, M = len(lock), len(key)
board = [[0] * (N + 2*M) for _ in range(N + 2*M)]
for i in range(N):
for j in range(N):
board[M+i][M+j] = lock[i][j]
for i in range(4):
key = rotate(key)
# 1에서 시작하는 이유?
# 1에서 board의 범위는 0 ~ N+2M
# 0부터 시작하게 되면 key랑 lock이 겹치는 부분이 하나도 없어서 의미가 없다.
# 마찬가지로 N+M은 겹치는 부분이 없고, N+M보다 큰 경우 범위인 N+2M의 범위를 넘기기 때문에 런타임 에러 발생
for i in range(1, N+M):
for j in range(1, N+M):
# board의 시작점이 i,j좌표.
if compare(board, key, i, j, M, N):
return True
return False
def rotate(key):
n = len(key)
rotate_key = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotate_key[j][n-i-1] = key[i][j]
return rotate_key
print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]], [[1, 1, 1], [1, 1, 0], [1, 0, 1]]))배운점
-
배열을 확장할 때 범위를 잘 고려해보자!
단순히 상하좌우를 3배만큼 팽창하여 접근했을 때, key의 길이가 20이고, lock의 범위가 3인 경우처럼 극단적으로 범위 차이가 있을 때 문제가 발생한다는 점도 확인해야 한다.
-
board에 key를 더하고 빼는 과정을 단순하게 생각하자!
코드를 작성하기 앞서 어떻게 작성하지?라는 생각에 이부분을 접근할 때 4중 포문으로 복잡하게 작성하여 조금 알아보기 힘들었다.
-> 효율성 검증이 없는 부분이니 접근할 때 완전 탐색으로도 생각해서 접근해보기.
-> N과 M의 최대 값이 20이므로, 20^4은 16만번으로 1초보다 훨씬 작다. -
시계 방향으로 90도씩 회전할 때 zip을 이용하게 편하게 작성하는 방법
def rotate(arr):
return list(zip(*arr[::-1]))