2022-09-18 알고리즘 기록
🥕 문제 접근
2022 KAKAO BLIND RECRUITMENT > (L3) 파괴되지 않은 건물
건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=python3
for문 3개로 접근했다. skill 배열, board 이차원 배열 ^__^
def solution(board, skill):
for s in skill:
# type, (r1, c1)~(r2, c2) 범위, degree
t, r1, c1, r2, c2, d = s
if t == 1: d *= (-1)
for i in range(r1, r2+1):
for j in range(c1, c2+1):
board[i][j] += d
answer = 0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] > 0: answer += 1
return answer결과는 정확성은 통과, 효율성은 실패 😢
암만 생각해도 for문 3개 사용에서 벗어나지 못하겠더라~
🥕 구글링 시도
그래서! 구글링을 시도했다 👍 그렇게 얻은 방식이 누진법 ㅇㅁㅇ ?!
skill의 영향을 누진법용 배열에 담아서, 마지막에 board 배열에 더하고 건물의 파괴 여부를 판단하는 방식이었다.
🥺 누진법용 배열을 만들어보자
- (r1, c1) 에서 (r2, c2) 까지 skill 영향을 받는다.
degree가 N이라고 하면, (r1, c1) ~ (r2, c2) 칸은 N이어야 한다.
위 조건을 만족시키고 최소한의 for문을 사용하기 위해서,
(r1, c1) , (r1, c2+1) , (r2+1, c1), (r2+1, c2+1) 위치에 스킬 정도(N)를 찍어준다. 그리고 행과 열 기준으로 당겨준다. (각 부호가 다른 이유는 (r1, c1) ~ (r2, c2) 범위를 벗어나는 칸은 스킬 정도가 0이어야 하기 때문이다.)
먼저 행 기준으로 당겼다.
남은 열 기준으로 당기면, 스킬 범위 내에만 N이 찍혔음을 확인할 수 있다.
위 배열 결과를 board 배열에 더해주면 모든 스킬 후의 board 배열 결과를 얻을 수 있다.
🥕 로직을 구현한 코드
def solution2(board, skill):
visited = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
# type, (r1, c1)~(r2, c2) 범위, degree
for t, r1, c1, r2, c2, degree in skill:
visited[r1][c1] += degree if t==2 else (-1)*degree
visited[r1][c2+1] += degree if t==1 else (-1)*degree
visited[r2+1][c1] += degree if t==1 else (-1)*degree
visited[r2+1][c2+1] += degree if t==2 else (-1)*degree
for j in range(len(board[0])):
for i in range(len(board)):
visited[i+1][j] += visited[i][j]
for i in range(len(board)):
for j in range(len(board[0])):
visited[i][j+1] += visited[i][j]
answer = 0
for i in range(len(board)):
for j in range(len(board[0])):
board[i][j] += visited[i][j]
if board[i][j] > 0: answer += 1
return answer누진법으로 시간 복잡도를 O(nxm)으로 줄일 수 있었다.
🥕 회고
어렵당 🥺 구글링 하고 싶지 않았지만, 구글링 하고 구글링 없이 절대 못 풀었을 문제를 인지해서 더 어렵다. 뿌앵 😢
누진법 진짜 신기하다. 기억해뒀다가 써먹어야겠다 😋
