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

 

프로그래머스

 

• 규칙
  • 내구도를 가진 건물이 각 칸마다 하나씩 존재
  • 적은 건물을 공격해 파괴 - 적의 공격을 받으면 내구도 감소
  • 내구도가 0 이하면 차괴
  • 아군은 회복 스킬을 사용해 내구도 높일 수 있음
  • (row, column) 형태
  • 파괴되었다가 복구 가능
• 데이터
  • 내구도 board 배열
  • 적의 공격 혹은 아군의 회복 스킬 skill 배열
    • skill은 [type, r1,c1,r2,c2,degree]
      • type: 적1 or 아군2
      • degree: 내구도 혹은 회복력
• 출력: 적의 공격과 아군의 회복 스킬이 모두 끝났을 때 파괴되지 않은 건물의 수 리턴

 

---

 

풀이

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    for (int i=0;i<skill.size();i++){
        int type = skill[i][0];
        
        int r1 = skill[i][1]; int c1 = skill[i][2];
        int r2 = skill[i][3]; int c2 = skill[i][4];
        
        int degree = skill[i][5];
        
        for (int c=c1;c<=c2;c++){
            for (int r=r1;r<=r2;r++){
                if (type == 1){ // 적
                    board[r][c] = board[r][c] - degree;
                } else if (type == 2){ // 아군
                    board[r][c] = board[r][c] + degree;
                }
            }
        }
    }
    
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board[i].size();j++){
            if(board[i][j]>0){
                answer+=1;
            }
        }
    }
    
    return answer;
}

 

시간초과가 걸릴 것 같았으나 일단 3중 for문을 돌려보았다.

 

역시나 결과는 효율성 빵점 ㅎ.ㅎ

 

 

다른 풀이를 찾아보니 누적합을 사용해야 한다는 것을 알 수 있었습니다!

 

 

코딩테스트 -- 파괴되지 않은 건물 - (프로그래머스 / C++) / 누적합

 

이 분의 티스토리를 참고했는데 티스토리에 누적합이 무엇인지 한 번에 이해할 수 있게 적어주셨어요!

저랑 같은 방법으로 풀이를 작성하셔서 시간초과로 인해 효율성 0점을 받으시고 누적합을 적용하신 것 같더라구요.

 

 

누적합이 무엇일까요?

현재부터 마지막까지의 합들을 빠르게 계산할 수 있는 방법으로, 현재 값을 기존 값+앞에서 합친 값으로 구현할 수 있습니다.

 

이렇게 쓰면 무슨 말인지 이해가 안되니 예시를 들어보겠습니다.

 

길이가 5인 1차원 배열이 주어졌을 때, 0에서 2번 인덱스까지 모든 값을 +2를 해야 한다는 예시입니다.

누적합을 사용해서 풀려면 주어진 배열은 [2,0,0,-2,0]이 됩니다.

왜 0번 인덱스의 값은 2이고, 3번 인덱스의 값은 -2가 되었을까요?

다음과 같은 이유 때문입니다.

 

0번 인덱스는 앞에서 합친 값이 없어 '2' 유지

1번 인덱스는 0번 인덱스까지의 합 + 1번 인덱스의 값 = 2+0 = '2'

2번 인덱스는 1번 인덱스까지의 합 + 2번 인덱스의 값 = 2+0 = '2'

3번 인덱스는 2번 인덱스까지의 합 + 3번 인덱스의 값 = 2+(-2) = '0'

4번 인덱스는 3번 인덱스까지의 합 + 4번 인덱스의 값 = 0+0 = '0'

이렇게 계산하면 배열은 [2,2,2,0,0]가 된다!

 

그럼 2차원 배열에서는 어떻게 적용될까?!

 

(4,4)인 2차원 배열이 주어졌을 때, (0,0)부터 (2,2)까지 +2를 해야 한다고 가정해 봅시다.

초기 배열은 [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]입니다.

누적합은 [[2,0,0,-2],[0,0,0,0],[0,0,0,0],[-2,0,0,2]] 배열을 이용합니다.

 

우선 행에 대해서 누적합을 적용해 봅시다.

[[2,2,2,0],[0,0,0,0],[0,0,0,0],[-2,-2,-2,0]] 이런 결과를 얻을 수 있습니다.

그 다음 열에 대해서 누적합을 적용해 봅시다.

2,2,2,0

2,2,2,0

2,2,2,0

0,0,0,0

이 되는 것을 알 수 있습니다.

 

자 이제 누적합을 적용해서 문제를 풀어봅시다!

 

---

 

풀이2️⃣ - 정답

#include <string>
#include <vector>

using namespace std;

int attack[1010][1010];

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    // 누적합할 배열 만들기
    for (int i=0;i<skill.size();i++){
        int type = skill[i][0];
        
        int r1 = skill[i][1]; int c1 = skill[i][2];
        int r2 = skill[i][3]; int c2 = skill[i][4];
        
        int degree = skill[i][5];
        if (type == 1) degree = degree * (-1);
            
        attack[r1][c1] += degree;
        attack[r1][c2+1] -= degree;
        attack[r2+1][c1] -= degree;
        attack[r2+1][c2+1] += degree;
    }
    
    // column 누적합 계산
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board[i].size();j++){
            attack[i][j+1] += attack[i][j];
        }
    }
    
    // row 누적합 계산
    for(int j=0;j<board[0].size();j++){
        for(int i=0;i<board.size();i++){
            attack[i+1][j] += attack[i][j];
        }
    }
    
    // 결과 배열
    for(int i=0;i<board.size();i++){
        for(int j=0;j<board[i].size();j++){
            if(attack[i][j] + board[i][j]>0){
                answer+=1;
            }
        }
    }
    
    return answer;
}

 

누적합 사용하니 효율성도 다 맞았습니다.

 

문제를 풀 때 인덱스가 헷갈릴 수 있으니 이것만 주의하면 누적합 적용해서 수월하게 해결 가능합니다!