[파이썬(python)] 2022 카카오 블라인드 공채 파괴되지 않은 건물

https://programmers.co.kr/learn/courses/30/lessons/92344

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

이 문제.. 구현은 간단한데 효율성 통과하기가 정말 어렵다. 남은 3문제중에 그나마 간단한 것 같아서 도전했으나 ..

한시간동안 고민해도 해결방법을 찾지 못함..

정확도는 모두 통과했다. 그러고나서 효율성을 통과하려고, 2차원 배열을 이어붙여서 1차원 배열로 바꾸는 방법을 도전해봤음....

그래도 시간초과가 났다 ㅜ

우선 내가 작성한 코드부터 올려본다.

 

 

내 코드의 문제점

효율성을 낮출려고 짠 코드인데도 결국 시간복잡도가 o(n*m*k)이다.

 

나는 r1,c1 ~ r2,c2까지 해당되는 인덱스를 반환하는 함수를 구현했는데

이것이 문제였다.

결국은 n*m*k의 시간복잡도가 여기서 발생한다....... 

 

def index(r1,c1,r2,c2,n,m):

#r1 c1 부터 r2 c2까지 해당되는 인덱스 반환
    idx = []
    for i in range(r1, r2+1):
        for j in range(c1, c2+1):
            idx.append(m*i+j)
        
    return idx

def solution(board, skill):
    answer = 0
    #skill.sort(key = lambda x:(x[0], -x[5]))
    n = len(board)
    m = len(board[0])
    
    board_1 = []
    
    for i in board:
        for j in i:
            board_1.append(j)

#o(n*m)
            
    for ty_pe, r1, c1, r2, c2, degree in skill:
        idx = index(r1,c1,r2,c2,n,m) #o(k*n*m)
        if ty_pe == 1:
            for i in idx:
                board_1[i] -= degree
        else:
            for i in idx:
                board_1[i] += degree
                
    for i in range(len(board_1)):
        if board_1[i] >= 1:
            answer += 1
        
    
    
                    
        
    return answer

 

답안

사실 모든 skill에 대해 처음부터 끝까지 degree의 총합을 계산한 다음,

board와 더해주는 방법을 생각하긴 했는데

어떻게 해도 시간복잡도가 그대로일것 같았는데 이런 방법이 있는줄 몰랐다.

 

만약 0,0 부터 3,4까지 3씩 더하고 싶으면,

3 0 0 0 0 -3

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

-3 0 0 0 0 3

이렇게만 마크해놓고 위아래로 누적합을 계산하면

 

3 3 3 3 3 0

3 3 3 3 3 0

3 3 3 3 3 0

3 3 3 3 3 0

0 0 0 0 0 0

 

이렇게 n*m의 시간복잡도로 누적합이 계산된다.

 

따라서 총 O(k+3*n*m)의 시간복잡도가 소요된다.

 

 

def solution(board, skill):
    answer = 0
    n = len(board) #행
    m = len(board[0]) #열
    board_sum = [[0]*(m+1) for _ in range(n+1)] #누적합 저장하는 배열
    
            
    for ty_pe, r1, c1, r2, c2, degree in skill:
        if ty_pe == 1:
            board_sum[r1][c1] -= degree
            board_sum[r1][c2+1] += degree
            board_sum[r2+1][c1] += degree
            board_sum[r2+1][c2+1] -= degree
        else:
            board_sum[r1][c1] += degree
            board_sum[r1][c2+1] -= degree
            board_sum[r2+1][c1] -= degree
            board_sum[r2+1][c2+1] += degree
                    
    for i in range(n):
        for j in range(1, m):
            #누적합 구하기. 왼쪽에서 오른쪽으로
            board_sum[i][j] += board_sum[i][j-1] #O(n*m)
            
    for i in range(1, n):
        for j in range(m):
            #누적합 구하기. 위에서 아래로
            board_sum[i][j] += board_sum[i-1][j] #O(n*m)
    
    for i in range(n):
        for j in range(m):
            board[i][j] += board_sum[i][j] #O(n*m)
            if board[i][j] > 0:
                answer += 1
        
                    
        
    return answer