프로그래머스 2023.09.07 (3Lv 파괴되지 않은 건물)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
문제가 길어서 해당 프로그래머스 '파괴되지 않은 건물' 문제 페이지를 확인해주세요.
코딩
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
vector<vector<int>> vecPrefix(board.size(), vector<int>(board[0].size(), 0));
int iType, iCol1, iRow1, iCol2, iRow2, iNum;
for (size_t i = 0; i < skill.size(); ++i)
{
iType = skill[i][0];
iCol1 = skill[i][1];
iRow1 = skill[i][2];
iCol2 = skill[i][3];
iRow2 = skill[i][4];
iNum = skill[i][5];
// 공격일 경우
if (iType == 1)
{
for (int i = iCol1; i <= iCol2; ++i)
{
vecPrefix[i][iRow1] += -1 * iNum;
if (iRow2 + 1 < board[0].size())
vecPrefix[i][iRow2 + 1] += iNum;
}
}
// 회복일 경우
else if (iType == 2)
{
for (int i = iCol1; i <= iCol2; ++i)
{
vecPrefix[i][iRow1] += iNum;
if (iRow2 + 1 < board[0].size())
vecPrefix[i][iRow2 + 1] += -1 * iNum;
}
}
}
for (size_t i = 0; i < board.size(); ++i)
{
int Prefix = 0;
for (size_t j = 0; j < board[i].size(); ++j)
{
Prefix += vecPrefix[i][j];
if (board[i][j] + Prefix > 0)
{
answer++;
}
}
}
return answer;
}해당 문제는 2차 행렬에서 특정 범위에 동일한 수치를 증가하거나 줄이면서 푸는 문제였다.
처음 문제를 봤을 때, 누적합을 이용해 푸는 문제라는 것을 알고있었지만, 어떻게 누적합을 이용해 풀지 감이 잡히지 않았다. (누적합은 단순히 변하지 않는 배열이 주어졌을 때, 특정 구간의 합이나, 누적합 배열이 주어졌을 때 특정 인덱스의 수를 구하는 것만 생각했었기 때문..)
단순히 문제를 풀려하면, for문으로 반복해가며, Idx 하나하나 수를 변경하는 방식이 있는데, 이러기 위해서는 Skill의 size()만큼 반복해 회복인지 공격인지 판단해 범위만큼 Idx를 접근하며, 수를 증감시켜주어야 하는데, 그러려면 반복횟수가 많기 때문에 당연히 시간초과로 실패할 것이다.
이때, 주어진 행렬이 연산 도중 바뀌지 않고, 특정 범위내 수를 동일하게 증감하기 때문에 누적합을 적용해 풀 수 있었다.
위 코드는 누적합을 다시 공부해서 짠 코드인데, 1차 배열에서 누적합을 사용하던 것 처럼 짰다.
때문에 행의 수가 많아지면, 행만큼 반복해서 누적합 배열을 만들기 때문에 행이 많아질 수록 효율이 떨어져 효율성 검사에서 실패했다.
처음에는 단순히 누적합만 사용하면 된다 생각했기에 효율성을 전혀 고려하지 않았다.
하지만 고민해보니 Skill의 size()만큼만 반복해도 행렬의 누적합을 만들 수 있기 때문에 코드를 다시 짰다.
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill) {
int answer = 0;
vector<vector<int>> vecPrefix(board.size(), vector<int>(board[0].size(), 0));
int iType, iCol1, iRow1, iCol2, iRow2, iNum;
for (size_t i = 0; i < skill.size(); ++i)
{
iType = skill[i][0];
iCol1 = skill[i][1];
iRow1 = skill[i][2];
iCol2 = skill[i][3];
iRow2 = skill[i][4];
iNum = skill[i][5];
// 공격일 경우
if (iType == 1)
{
vecPrefix[iCol1][iRow1] += -1 * iNum;
if (iCol2 + 1 < vecPrefix.size() && iRow2 + 1 < vecPrefix[0].size())
vecPrefix[iCol2 + 1][iRow2 + 1] += -1 * iNum;
if (iRow2 + 1 < vecPrefix[0].size())
vecPrefix[iCol1][iRow2 + 1] += iNum;
if (iCol2 + 1 < vecPrefix.size())
vecPrefix[iCol2 + 1][iRow1] += iNum;
}
// 회복일 경우
else if (iType == 2)
{
vecPrefix[iCol1][iRow1] += iNum;
if (iCol2 + 1 < vecPrefix.size() && iRow2 + 1 < vecPrefix[0].size())
vecPrefix[iCol2 + 1][iRow2 + 1] += iNum;
if (iRow2 + 1 < vecPrefix[0].size())
vecPrefix[iCol1][iRow2 + 1] += -1 * iNum;
if (iCol2 + 1 < vecPrefix.size())
vecPrefix[iCol2 + 1][iRow1] += -1 * iNum;
}
}
// 동일행 다른 열들의 누적합 구하기
for (size_t i = 0; i < vecPrefix.size(); ++i)
{
int Prefix = 0;
for (size_t j = 0; j < vecPrefix[0].size(); ++j)
{
Prefix += vecPrefix[i][j];
vecPrefix[i][j] = Prefix;
}
}
// 동일열 다른 행들의 누적합 구하기
for (size_t j = 0; j < vecPrefix[0].size(); ++j)
{
int Prefix = 0;
for (size_t i = 0; i < vecPrefix.size(); ++i)
{
Prefix += vecPrefix[i][j];
vecPrefix[i][j] = Prefix;
}
}
for (size_t i = 0; i < board.size(); ++i)
{
for (size_t j = 0; j < board[i].size(); ++j)
{
if (board[i][j] + vecPrefix[i][j] > 0)
{
answer++;
}
}
}
return answer;
}사실 아직 코드만 봐서는 어느게 더 결과를 빠르게 구할지 감이 잘 안잡힌다.
하지만 문제에서 주어진 최악의 경우로 생각해보면, 첫 번째 코드보다 두 번째 코드가 수행횟수가 보다 적다.
정확성 테스트 결과를 보면 알겠지만, 행과 열이 최대 100일 경우, 주어지는 skill 배열이 최대 100일 경우 두 코드는 결과 차이가 크게 나지 않는다.
하지만, 효율성 테스트에서 주어지는 최악의 경우는 보다 커지므로 두번 째 코드가 더 효율적인거 같다.
조금 생각이 많아지는 것은 만약 정확성 테스트 최악의 경우를 생각해보면, 오히려 첫 번째 코드가 수행횟수가 적은게 아닌가 하는 생각이 들어서 정확히는 모르겠다..
짠 코드가 얼만큼 효율적이고, 예상 소요시간이 어느정도 걸리는지를 파악할 수 있도록 공부를 더 할 필요를 느낀다..
24.04.11 에 다시 풀어봤는데, 기존의 코드에서 보다 간결하게 짜보았다.
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> board, vector<vector<int>> skill)
{
int answer = 0;
vector<vector<int>> vecMemo(board.size() + 1, vector<int>(board[0].size() + 1, 0));
int iType, iRow1, iRow2, iCol1, iCol2, iDegree;
for (size_t i = 0; i < skill.size(); ++i)
{
iType = skill[i][0];
iRow1 = skill[i][1];
iCol1 = skill[i][2];
iRow2 = skill[i][3];
iCol2 = skill[i][4];
iDegree = iType == 1 ? iDegree = -skill[i][5] : iDegree = skill[i][5];
vecMemo[iRow1][iCol1] += iDegree;
vecMemo[iRow2 + 1][iCol2 + 1] += iDegree;
vecMemo[iRow1][iCol2 + 1] -= iDegree;
vecMemo[iRow2 + 1][iCol1] -= iDegree;
}
for (size_t i = 0; i < board.size(); ++i)
{
for (size_t j = 0; j < board[0].size(); ++j)
{
vecMemo[i][j + 1] += vecMemo[i][j];
}
}
for (size_t j = 0; j < board[0].size(); ++j)
{
for (size_t i = 0; i < board.size(); ++i)
{
vecMemo[i + 1][j] += vecMemo[i][j];
if (board[i][j] + vecMemo[i][j] > 0)
answer++;
}
}
return answer;
}삼항연산자를 이용해 공격/회복 수치를 + 혹은 -로 받아둔 뒤, 이후 큰 if문을 하나로 묶어주었다.
또한, 기존의 if문으로 기록하려는 vector에 인덱스를 넘어가는지 판단하지 않기 위해서 vecMemo를 만들때, board의 사이즈 보다 1을 더 증가시켜 만들어 굳이 if문으로 확인해 예외처리를 해주지 않아도 문제가 발생하지 않도록 만들었다.
누적합을 할 때는 본인을 다음번에 확인할 인덱스 원소에 더해주도록 만들었다.
또, 누적합을 마친 후 for문을 한번 더 사용해 파괴되지 않은 건물을 찾지 않고, 누적합의 마지막 for문에서 함께 처리해주도록 만들었다.
실행 결과
