[프로그래머스/C++] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT)

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

단순히 각 구간에 계산을 전부 해주면 250,000*1,000*1000이 되어 시간을 초과하게 된다.

그래서 구간을 전부 계산하는 것이 아닌, 시작 부분과 끝나는 부분에만 숫자를 더해 누적합으로 풀면 된다.

예를 들어 스킬이 [0,5,5,5,5,0]과 같이 데미지가 들어간다면, 이를 [0,5,0,0,0,-5]와 같이 표시할 수 있는 것이다.

 

이를 2차원으로도 확장 시킬 수 있는데

 

아래와 같이 변환 할 수 있다.

 

오른쪽의 변환된 정보를 x 축 기준으로 누적합을 계산한 다음 y축을 따라 다시 누적합을 계산하면 왼쪽과 같은 형태가 된다.

아래와 같은 순서로 압축

 압축한 정보를 이용할 경우는 아래와 같이 압축해제

모든 Skill에 대한 degree가 정리되면 압축한 정보를 해제해 건물의 내구도가 남아있는지 확인하면 된다.

​

[아이디어 정리]

1. 스킬의 시작 범위와 끝 범위를 이용해 누적합으로 표현한다.
2. 누적합을 2차원으로 확장해 기록의 횟수를 줄인다.
3. 누적합으로 skill의 degree가 전부 계산이 되면 내구도가 남아있는 건물의 수를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0, y = board.size(), x = board[0].size();
    vector<vector<int>>skillDamage(y,vector<int>(x,0));
    vector<vector<int>>damageRec(y,vector<int>(x,0));
    for (int i=0; i<skill.size();i++)
    {
        int d=skill[i][5];
        if (skill[i][0]==2)
        {
            d*=-1;
        }
        skillDamage[skill[i][1]][skill[i][2]]+=d;
        if (skill[i][4]+1<x)
        {
            skillDamage[skill[i][1]][skill[i][4]+1]-=d;
        }
        if (skill[i][3]+1<y)
        {
            skillDamage[skill[i][3]+1][skill[i][2]]-=d;
            if (skill[i][4]+1<x)
            {
                skillDamage[skill[i][3]+1][skill[i][4]+1]+=d;
            }
        }
    }
    for (int i=0; i<y; i++)
    {
        for (int j=1; j<x; j++)
        {
            skillDamage[i][j]+=skillDamage[i][j-1];
        }
    }
    for (int j=0; j<x; j++)
    {
        for (int i=1; i<y; i++)
        {
            skillDamage[i][j]+=skillDamage[i-1][j];
            if (skillDamage[i][j]<board[i][j])
            {
                answer+=1;
            }
        }
    }
    for (int j=0; j<x; j++)
    {
        if (skillDamage[0][j]<board[0][j])
        {
            answer+=1;
        }
    }
    return answer;
}

 

---

 

 

간만에 생각을 많이 해야했던 문제다.

처음에 어떻게 하면 정보를 압축할 수 있을까? 생각하다보니 스킬이 적용되는 시작부분에 스킬의 degree를 적용시키고, 끝나는 지점을 표시하면 압축 할 수 있겠다는 생각이 들었다.

 

하지만 y축을 기준으로 압축해도 효율성 테스트에서 250,000 *1000 의 경우가 남아있어 해결되지 않았다.

2차원의 경우 연속적이지 않아 보이는데 어떻게 압축을 해야하지 고민을 하다가 다른 사람들의 힌트를 참고했더니, 1차원으로 압축했던 것을 그냥 2차원으로 확장시키면 됐다...

 

2차원으로 그냥 확장시키면 되는데, 2차원을 1차원으로 연속적이게 바꿔야하나 생각하고 있었다니 어휴;; 더 많이 문제를 풀어봐야지...

 

프로그래머스