프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
코딩테스트 연습
기초부터 차근차근, 직접 코드를 작성해 보세요.
programmers.co.kr
문제
https://programmers.co.kr/learn/courses/30/lessons/60059
코딩테스트 연습 - 자물쇠와 열쇠
[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true
programmers.co.kr
내가 작성한 코드
def expand(lock, M):
N = len(lock)
for i in range(N):
lock[i] = [1 for _ in range(M-1)] + lock[i] + [1 for _ in range(M-1)]
N = len(lock[0])
lock = [[1 for _ in range(N)] for _ in range(M-1)] + lock + [[1 for _ in range(N)] for _ in range(M-1)]
return lock
def is_done(lock, N, M):
for i in range(M - 1, M - 1 + N):
for j in range(M - 1, M - 1 + N):
if lock[i][j] != 1:
return False
return True
def add(lock, key, r, c, M):
for i in range(r, r+M):
for j in range(c, c+M):
lock[i][j] += key[i-r][j-c]
def sub(lock, key, r, c, M):
for i in range(r, r+M):
for j in range(c, c+M):
lock[i][j] -= key[i-r][j-c]
def rotate(key, M):
return [[ row[j] for row in key ] for j in range(M-1, -1, -1)]
def solution(key, lock):
M = len(key)
N = len(lock)
lock = expand(lock, M)
for d in range(4):
key = rotate(key, M)
for r in range(len(lock) - M + 1):
for c in range(len(lock) - M + 1):
add(lock, key, r, c, M)
if is_done(lock, N, M):
return True
sub(lock, key, r, c, M)
return False
- expand
- N-1만큼 lock의 위, 아래, 왼쪽, 오른쪽을 늘리기
- 전체 탐색시, lock의 (0,0)과 key의 (N-1, N-1)부터 탐색 시작
- rotate
- key를 반시계방향으로 돌림
- add
- 현재 위치의 lock에 key를 더함
- is_done
- 실제 lock 범위가 모두 1인지 확인
- sub
- add했던 key 제거
다른 사람이 작성한 코드
None
기억해야할 것
- 데이터 범위가 작으면 전체 탐색 고려 (3 <= N, M <= 20)
- 문제의 비효율성보다 명확한 알고리즘을 고려하자
'코딩테스트' 카테고리의 다른 글
[프로그래머스][KAKAO_BLIND][2019] 후보키 (0) | 2021.08.30 |
---|---|
[프로그래머스][KAKAO_BLIND][2019] 실패율 (0) | 2021.08.30 |
[프로그래머스][KAKAO_BLIND][2019] 오픈채팅방 (0) | 2021.08.29 |
[프로그래머스][KAKAO_BLIND][2021] 카드 짝 맞추기 (0) | 2021.08.26 |
[프로그래머스][KAKAO_BLIND][2021] 합승 택시 요금 (0) | 2021.08.25 |