[프로그래머스] 파괴되지 않은 건물

2022 KAKAO BLIND RECRUITMENT

파괴되지 않은 건물

누적합

---

※ 카카오 공식 해설

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

 

 

[문제]

적의 공격 및 아군의 회복은 직사각형 형태

 

내구도는 음수도 될 수 있음

 

여러차례의 공격 및 회복이 끝나면 내구도가 0보다 큰 건물의 개수를 반환하면 되는 문제

 

 

우선 문제풀이에 앞서 시간복잡도부터 계산하도록 하자.

기본적으로 1억의 연산은 1초의 시간이 소요된다.

해당 문제는 최악의 경우에 1,000 x 1,000 x 25.,000 = 250,000,000,000의 시간이 소요됨을 알 수 있다.

즉, 브루트포스로 풀게 되는 경우에는 O(N x M x K)이 되고 정확성 테스트에는 통과되지만 효율성 테스트케이스에서 시간 초과가 발생하게 된다.

(내 이야기다ㅎㅎ)

 

누적합 알고리즘으로 풀 경우 O(K + N x M)이 되어서 통과가 가능하다.

자세한 설명은 카카오 공식해설에서 이해하기 쉽게 자세히 설명해주니 참고하면 좋다.

(나의 경우도 효율성에서 틀린 후 해설을 참고해서 코드를 짜서 통과했다)

 

---

[과정]

기본 방식은 누적합을 2차원 배열로 늘려서 사용해 시간복잡도를 줄이는 형태

 

※ 누적합

[1차원의 경우]

카카오 공식 해설

[2차원의 경우]

2차원 배열에서 (0,0)부터 (2,2)까지 n만큼 변화시키는 경우

 

---

 

• 누적합 2차원 배열 0으로 초기화 (오른쪽으로 한칸 이동해야 하므로 N+1만큼의 크기로 생성)
• 타입을 비교 후 degree만큼의 값을 누적합 공식을 통해 더하고 빼줌
  • prefix_arr[r1][c1] = prefix_arr[r1][c1] + degree       (x1,y1)에 +n
  • prefix_arr[r1][c2+1] = prefix_arr[r1][c2+1] - degree        (x1,y2+1)에 -n
  • prefix_arr[r2+1][c1] = prefix_arr[r2+1][c1] - degree        (x2+1,y1)에 -n
  • prefix_arr[r2+1][c2+1] = prefix_arr[r2+1][c2+1] + degree       (x2+1,y2+1)에 +n
• 위에서 아래로 누적합
• 왼쪽에서 오른쪽으로 누적합
• board에서 0보다 큰 정수의 개수 구하기

 

---

[소스코드]

 

def prefix_sum(tmp_board, skill):
    # 누적합 2차월 배열 초기화
    prefix_arr = [[0 for j in range(len(tmp_board[0])+1)] for i in range(len(tmp_board)+1)]
    
    # 누적합 배열 생성
    for s in skill:
        t, r1, c1, r2, c2, degree = s  
        if t == 1:    # 타입 비교
            degree = -degree
        prefix_arr[r1][c1] = prefix_arr[r1][c1] + degree  # (x1,y1)에 +n
        prefix_arr[r1][c2+1] = prefix_arr[r1][c2+1] - degree   # (x1,y2+1)에 -n
        prefix_arr[r2+1][c1] = prefix_arr[r2+1][c1] - degree   # (x2+1,y1)에 -n
        prefix_arr[r2+1][c2+1] = prefix_arr[r2+1][c2+1] + degree   # (x2+1,y2+1)에 +n
    
    # 위에서 아래로 누적합
    for i in range(len(prefix_arr)):
        for j in range(len(prefix_arr)-1):
            prefix_arr[j+1][i] += prefix_arr[j][i]
    
    # 왼쪽에서 오른쪽으로 누적합
    for i in range(len(prefix_arr)):
        for j in range(len(prefix_arr)-1):
            prefix_arr[i][j+1] += prefix_arr[i][j]
    
    return prefix_arr

def solution(board, skill):
    answer = 0
    prefix_board = prefix_sum(board, skill)
    
    # 누적합 합산
    for i in range(len(board)):
        for j in range(len(board[0])):
            board[i][j] += prefix_board[i][j]
            # 0보다 큰 정수의 개수 구하기
            if board[i][j] > 0:
                answer += 1
    
    return answer

 

 

[통과]

 

---

[브루트포스로 푼 코드]

 

def calculate_durability(tmp_board, skill):
    for s in skill:
        t, r1, c1, r2, c2, degree = s  
        for i in range(r1,r2+1):
            for j in range(c1, c2+1):
                if t == 1:
                    tmp_board[i][j] = tmp_board[i][j] - degree
                else: tmp_board[i][j] = tmp_board[i][j] + degree       
    return tmp_board 
   
def check_durability(result_board):
    cnt = 0
    for i in range(len(result_board)):
        for j in range(len(result_board[0])):
             if result_board[i][j] > 0:
                cnt += 1
    return cnt

def solution(board, skill):
    answer = 0
    result_board = calculate_durability(board, skill)
    answer = check_durability(result_board)       
    return answer