[Python] 파괴되지 않은 건물

1. 문제

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

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

 

 

2. 회고

• 누구나 그랬겠지만 보자마자 쉽네? 했다가 효율성 무슨일..ㅋㅋ
• 누적합 을 사용하는 문제

누적합이란?

리스트 l = [0,0,0,0,0,0] 이라고 둘 때, 리스트 [0] 부터 [3] 을 1로 바꾸어야 한다면 어떻게 할까?

• 보통 우리는 for 문을 0부터 3까지 돌려 [1,1,1,1,0,0]으로 바꿀 것이다.
• 그런데 누적합은 시작점과 끝점에 표시하는 것으로 위의 배열을 나타낼 수 있다.

l = [0,0,0,0,0,0] 일때 타겟이 [1,1,1,1,0,0]이라면, multisum_l = [1,0,0,0,-1,0]

• 이때 누적합을 전개하면, 즉 현재의 값에 이전의 값을 더하면

l[i] += l[i-1] 
=> 결과 
multisum = [1,1,0,0,-1,0] 
multisum = [1,1,1,0,-1,0] 
multisum = [1,1,1,1,-1,0] 
multisum = [1,1,1,1,0,0] 
multisum = [1,1,1,1,0,0] <- target

즉 누적합은 시작과 끝에 표시하는 것으로 연속된 수를 표현할 수 있다.

 

이차원 배열에서 누적합

• 이차원 배열에서는 가로로 한번, 세로로 한번 전개를 해주어야 한다.
• 따라서 시작점과 끝점을 신경써서 표시해주면 된다.

예를 들어, (r1,c1) 부터 (r2,c2)까지 degree만큼 더해주고 싶을 때

multisum_list[r1][c1] += degree 
multisum_list[r1][c2+1] -= degree 
multisum_list[r2+1][c1] -= degree 
multisum_list[r2+1][c2+1] += degree

 

다음과 같이 시작점에 degree를 더하고, 끝점 +1 인 지점에 degree를 빼준 뒤,

 

가로로 전개

for i in range(len(board)): 
	for j in range(1,len(board[0])): 
   		multisum_list[i][j] += multisum_list[i][j-1]

세로로 전개

for i in range(len(board[0])): 
	for j in range(1,len(board)): 
		multisum_list[j][i] += multisum_list[j-1][i]

해주면 된다.

 

이렇게 누적합을 사용한다면, 처음에 skill 배열의 크기만큼 돌리며 시작점과 끝점을 표시하고,

NxM 보드를 채워주면 되니 최악의 경우 시간복잡도는 O(N*M) 이 된다.

그러나 누적합을 사용하지 않는다면, 배열 점 마다 skill에 해당이 되는지 확인해야 하므로,

최악의 경우 시간복잡도는 O(N*M*skill)이 된다.

 

 

3. 코드

# 효율성 안나오는 틀린코드
def solution1(board, skill):
    answer = 0
    board_list = board[:]
    for x in range(len(board_list)):
        for y in range(len(board_list[0])):
            print("x, y : ",x,y)
            for i in skill:
                r1,c1,r2,c2,degree = i[1],i[2],i[3],i[4],i[5]
                if (x >= r1 and x<= r2)and(y>=c1 and y<=c2):
                    # 공격스킬
                    if i[0] == 1:
                        board_list[x][y] += degree
                        print("get  ",x,y)          
                    # 방어스킬
                    else:
                        board_list[x][y] -= degree       
            if board_list[x][y] > 0:
                answer += 1
    print(answer)
    return answer

# 이게 정답코드 
def solution2(board, skill):
    answer = 0
    board_list = board[:]
    # 누적합 배열
    multisum_list = [[0]*(len(board_list[0])+1) for i in range(len(board_list)+1)]
    
    for i in skill:
        r1,c1,r2,c2,degree = i[1],i[2],i[3],i[4],i[5]
        # 공격스킬
        if i[0] == 1:
            multisum_list[r1][c1] -= degree 
            multisum_list[r1][c2+1] += degree    
            multisum_list[r2+1][c1] += degree    
            multisum_list[r2+1][c2+1] -= degree    
        # 방어스킬
        else:
            multisum_list[r1][c1] += degree 
            multisum_list[r1][c2+1] -= degree    
            multisum_list[r2+1][c1] -= degree    
            multisum_list[r2+1][c2+1] += degree   

    # 누적합 가로 진행
    for i in range(len(board)):
        for j in range(1,len(board[0])):
            multisum_list[i][j] += multisum_list[i][j-1]
    
    # 누적합 세로 진행
    for i in range(len(board[0])):
        for j in range(1,len(board)):
            multisum_list[j][i] += multisum_list[j-1][i]
            
    for x in range(len(board)):
        for y in range(len(board[0])): 
            if board_list[x][y] > (multisum_list[x][y]* -1):
                answer += 1
    
    return answer