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

문제 : 

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

프로그래머스

 

 

나의 풀이

- board 값을 복사하여 내구도 값을 저장한다.

- type이 1인 경우(적의 공격)만 확인하고 해당 범위의 내구도 값을 빼준다. 최종적으로 1 이하인 값만 리스트에 (행, 열) 번호를 저장한다.

- type이 2인 경우에서 최종 내구도 값이 1 이하인 값만 회복 스킬 값을 더해주고, 값이 1 이상이 되면 리스트에 (행,열) 번호를 저장한다.

- 위에서 저장한 두 리스트를 집합 형태로 바꿔서 중복을 제거한다.

- 최종적으로 전체 board 크기 값에서 첫번째 리스트 길이 값(type 1 내구도 1 이하 값)을 빼주고 두 번째 리스트 길이 값(type 2 내구도 1 이상 값)을 더해 리턴한다.

 

-> 결과 : 정확성 맞음, 효율성 0점

-> 시간복잡도 : O(N*M)

def solution(board, skill):
    answer = 0
    check = board.copy()
    arr = []
    arr1 = []
    for s in skill:
        if s[0] == 1:
            for r in range(s[1],s[3]+1):
                for c in range(s[2],s[4]+1):
                    check[r][c] -= s[5]
                    if check[r][c] < 1:
                        arr.append((r,c))
                    
    for s in skill:
        if s[0] == 2:
            for r in range(s[1],s[3]+1):
                for c in range(s[2],s[4]+1):
                    if check[r][c] < 1:
                        check[r][c] += s[5]
                        if check[r][c] >= 1:
                            arr1.append((r,c))
    
    temp = set(arr)
    temp1 = set(arr1)
    
    return len(board[0]) * len(board) - len(temp) + len(temp1)

 

 

정답 풀이

- 누적 합 이용하여 전부 탐색하는 과정 O(N)에서 O(1)로 해결한다.

- 누적 합을 저장할 2차원 배열은 행, 열 각각 길이 +1로 만든다.

- 아래 사진 방식 1번과 같이 2차원 배열에 내구도 값을 저장한다.

- 행 기준 누적 합과 열 기준 누적 합을 계산한다.

- 기존 값과 누적 합 값을 더하여 내구도 값이 1 이하인지 확인한다.

 

(0,0) ~ (3,3) -N 누적 합 구하기

 

def solution(board, skill):
    answer = 0
    tmp = [[0]*(len(board[0])+1) for _ in range(len(board)+1)]

    for type, r1,c1,r2,c2,degree in skill:
        tmp[r1][c1] += degree if type ==2 else -degree
        tmp[r1][c2+1] += -degree if type==2 else degree
        tmp[r2+1][c1] += -degree if type==2 else degree
        tmp[r2+1][c2+1] += degree if type==2 else -degree
        
    #행 기준 누적합
    for i in range(len(tmp)-1):
        for j in range(len(tmp[0])-1):
            tmp[i][j+1] += tmp[i][j]

    #열 기준 누적합
    for j in range(len(tmp[0])-1):
        for i in range(len(tmp)-1):
            tmp[i+1][j]+=tmp[i][j]

    #기존 배열과 합함
    for i in range(len(board)):
        for j in range(len(board[0])):
            board[i][j] += tmp[i][j]
            # board에 값이 1이상인 경우 answer++
            if board[i][j] > 0: answer += 1
    
    return answer

 

+ 누적 합 참고

https://minjoo-happy-blog.tistory.com/96

[Algorithm] 누적 합(Prefix Sum, Cumulative Sum)