1. 파괴되지 않은 건물
- 난이도
- Level 3
- 출처
A. 📜 문제
위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.
B. 💡 내 답안
a. 😅 1차 시도 (실패)
def check_undestroy(board):
count = 0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] > 0:
count += 1
return count
def solution(board, skill):
for s in skill:
t, r1, c1, r2, c2, degree = s
for r in range(r1, r2 + 1):
for c in range(c1, c2 + 1):
if t == 1:
board[r][c] -= degree
elif t == 2:
board[r][c] += degree
return check_undestroy(board)
# 채점 결과
#
# 정확성: 53.8
# 효율성: 0.0
# 합계: 53.8 / 100.0
b. 😊 2차 시도 (성공)
def solution(board, skill):
count = 0
imos = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
for s in skill:
t, r1, c1, r2, c2, degree = s
# 공격
if t == 1:
imos[r1][c1] -= degree
imos[r1][c2 + 1] += degree
imos[r2 + 1][c1] += degree
imos[r2 + 1][c2 + 1] -= degree
# 회복
elif t == 2:
imos[r1][c1] += degree
imos[r1][c2 + 1] -= degree
imos[r2 + 1][c1] -= degree
imos[r2 + 1][c2 + 1] += degree
for row in range(len(imos)):
for column in range(1, len(imos[0])):
imos[row][column] += imos[row][column - 1]
for column in range(len(imos[0])):
for row in range(1, len(imos)):
imos[row][column] += imos[row - 1][column]
for row in range(len(board)):
for column in range(len(board[0])):
board[row][column] += imos[row][column]
if board[row][column] > 0:
count += 1
return count
# 채점 결과
#
# 정확성: 53.8
# 효율성: 46.2
# 합계: 100.0 / 100.0
a. 🙄 회고
내 풀이
- imos 알고리즘을 사용했다.
- imos 알고리즘은 다차원 누적합이다.
결론
- 새로운 알고리즘 문제는 어렵다.
- 다만, 익히면 쉬워진다.
C. 🧐 문제 해설
이해한 내용을 바탕으로 작성했습니다.
이렇게 풀면, 시간복잡도가 확 줄어든다.
1차 시도에서는 O(skill_n * board_n^2). 즉, O(250,000 * 1,000 * 1,000)이고,
2차 시도에서는 O(skill_n + 2*((board_n+1)^2) + (board_n)^2) = O(skill_n + (board_n+1)^2 + board_n^2) = O(250,000 + (1001)^2 + 1000^2) 이다.
즉, O(n*m^2)이던 시간복잡도가 O(n+2(m^2) 정도로 줄어든 것을 알 수 있다.
참고문헌
2022 KAKAO BLIND RECRUITMENT. 코딩테스트 연습 - 파괴되지 않은 건물 | 프로그래머스 (programmers.co.kr). Programmers. (accessed Feb 17, 2022)
Ghost