[프로그래머스] 코딩테스트 연습 - 파괴되지 않은 건물 (Python)

코딩테스트 연습 - 파괴되지 않은 건물 [2022 KAKAO BLIND RECRUITMENT]

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

해당 문제 해설은 카카오 사이트에 올라와 있으니 참고하시면 좋을 것 같습니다.

 

풀이

해당 문제의 효율성을 통과하는 방법에서 가장 중요한 키워드는 누적합입니다.

문제를 보고 브루트 포스 방법을 사용하면 정확성은 통과할 수 있겠다는 생각이 듭니다.

하지만 효율성을 통과하기 위해서 누적 합의 개념을 사용해야 합니다.

 

[1, 2, 3, 4, 5]인 1차원 배열인 board에 아래와 같은 시나리오를 적용시켜 보겠습니다.

1. 0번부터 4번까지 1의 강도로 공격

2. 1번부터 3번까지 2의 강도로 회복

시나리오 1번 [-1, 0, 0, 0, 0, 1]
시나리오 2번 [-1, 2, 0, 0, -2, 1]
누적합 결과  [-1, 1, 1, 1, -1, 0]

그리고 누적합 결과배열을 board에 그대로 더해준다면 [0, 3, 4, 5, 4]가 되어 모든 시나리오를 진행한 것과 같아집니다.

그러면 N범위를 갖는 시나리오를 M개 적용했다고 쳤을 때 범위에 대한 복잡도가 O(1)이 되어 O(M)의 시간 안에 해결할 수 있습니다.  

 

그렇다면 2차원배열에는 어떠한 방식으로 누적합을 적용시켜야 할까요.

행과 열에 대한 누적합을 따로 적용시켜 주면 됩니다.

3x3 크기의 배열에 (0,0)부터 (2,2)까지 1의 강도로 공격한다면 다음과 같아집니다.

[[-1, 0, 0, 1],
 [-1, 0, 0, 1],
 [-1, 0, 0, 1]]

하지만 위의 방법을 사용하면 행만큼 반복해주어야 합니다.

그러니 위에서 누적 합의 아이디어를 한 번 더 적용시키면 아래와 같아집니다.

[[-1, 0, 0, 1 ],
 [ 0, 0, 0, 0 ],
 [ 0, 0, 0, 0 ],
 [ 1, 0, 0, -1]]

이것을 세로 방향으로 누적한 뒤에 가로 방향으로 누적하면 총 공격해야 하는 범위와 공격이 나오게 되는 것이죠.

 

Code

 

def solution(board, skill):
    answer = 0
    row, col = len(board)+1, len(board[0])+1
    record = [[0 for i in range(col)] for j in range(row)]

    for type, r1, c1, r2, c2, d in skill:
        newd = d if type==2 else -d # degree
        r2, c2 = r2+1, c2+1
        record[r1][c1] += newd      # left, top
        record[r2][c1] += -newd     # right, top
        record[r1][c2] += -newd     # left, bottom
        record[r2][c2] += newd      # right, bottom

    for r in range(1, row):     # row 누적
        for c in range(col):
            record[r][c] += record[r-1][c]

    for r in range(row):        # col 누적
        for c in range(1, col):
            record[r][c] += record[r][c-1]

    for r in range(row-1):      # board에 누적합 적용
        for c in range(col-1):
            board[r][c] += record[r][c]
            answer += 1 if board[r][c]>0 else 0

    return answer

 

 

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

 

 

제한사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

 

 

입출력 예

board	skill	result
[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]]	[[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]]	10
[[1,2,3],[4,5,6],[7,8,9]]	[[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]	6