Level 3 파괴되지 않은 건물 <2022 KAKAO BLIND RECRUITMENT> Python 3

https://programmers.co.kr/learn/courses/30/lessons/92344?language=python3 

코딩테스트 연습 - 파괴되지 않은 건물

 

최종 코드

• Github - https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_파괴되지않은건물.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

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