728x90
반응형
https://programmers.co.kr/learn/courses/30/lessons/92344?language=python3
최종 코드
def solution(board, skill):
answer = 0
skills = [[0] * (len(board[0])+1) for _ in range(len(board) + 1)]
for t, r1, c1, r2, c2, d in skill:
if t == 1:
skills[r1][c1] -= d
skills[r1][c2 + 1] += d
skills[r2 + 1][c1] += d
skills[r2+1][c2 + 1] -= d
else:
skills[r1][c1] += d
skills[r1][c2 + 1] -= d
skills[r2 + 1][c1] -= d
skills[r2 + 1][c2 + 1] += d
for c in range(len(board[0])+1):
n_sum = 0
for r in range(len(board)+1):
skills[r][c] += n_sum
n_sum = skills[r][c]
for r in range(len(board)+1):
n_sum = 0
for c in range(len(board[0])+1):
skills[r][c] += n_sum
n_sum = skills[r][c]
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] + skills[r][c] > 0: answer += 1
return answer
풀이 과정
def solution(board, skill):
answer = 0
#모든 스킬을 적용한 값을 저장하는 (N+1, M+1) 크기의 리스트 초기화
skills = [[0] * (len(board[0])+1) for _ in range(len(board) + 1)]
for t, r1, c1, r2, c2, d in skill:
#공격인 경우,
if t == 1:
skills[r1][c1] -= d
skills[r1][c2 + 1] += d
skills[r2 + 1][c1] += d
skills[r2+1][c2 + 1] -= d
#회복인 경우,
else:
skills[r1][c1] += d
skills[r1][c2 + 1] -= d
skills[r2 + 1][c1] -= d
skills[r2 + 1][c2 + 1] += d
#위에서 아래로 누적합 적용
for c in range(len(board[0])+1):
n_sum = 0
for r in range(len(board)+1):
skills[r][c] += n_sum
n_sum = skills[r][c]
#왼쪽에서 오른쪽으로 누적합 적용
for r in range(len(board)+1):
n_sum = 0
for c in range(len(board[0])+1):
skills[r][c] += n_sum
n_sum = skills[r][c]
#파괴되지 않은 건물 수 구하기
for r in range(len(board)):
for c in range(len(board[0])):
if board[r][c] + skills[r][c] > 0: answer += 1
return answer
#시간복잡도 = O(len(skill) + N*M), 공간복잡도 = O(N*M)
오답 노트
- 정확성만 맞은 코드
최악의 경우, O(1000*1000*250000)만큼 소요된다.
def solution(board, skill):
answer = 0
skills = [[0]*len(board[0]) for _ in range(len(board))]
for t, r1, c1, r2, c2, d in skill:
for r in range(r1, r2+1):
for c in range(c1, c2+1):
if t == 1:
skills[r][c] -= d
else:
skills[r][c] += d
for r in range(len(board)):
for c in range(len(board[0])):
if skills[r][c] + board[r][c] > 0: answer += 1
return answer
728x90
반응형
'코테 노트 > 프로그래머스' 카테고리의 다른 글
Level 3 블록 이동하기 <2020 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.05.06 |
---|---|
Level 3 양과 늑대 <2022 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.05.06 |
Level 3 카드 짝 맞추기 <2021 KAKAO BLIND RECRUITMENT> Python3 (0) | 2022.05.06 |
Level 3 광고 삽입 <2021 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.05.05 |
Level 3 외벽 점검 <2020 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.04.07 |