문제 소개
n개의 열과 2개의 행으로 구성된 행렬에 대해 다음과 같은 정보가 주어진다고 가정해 보겠습니다.
- 행렬의 모든 요소는 0 또는 1이어야 합니다.
- 0번째(위쪽) 행에 있는 요소들의 합은 upper로 주어집니다.
- 1번째(아래쪽) 행에 있는 요소들의 합은 lower로 주어집니다.
- i번째 열(0부터 시작하는 인덱스 기준)에 있는 요소들의 합은 colsum[i]이며, colsum은 길이가 n인 정수 배열로 주어집니다.
이때 주어진 upper, lower, colsum 정보를 바탕으로 원래의 행렬을 재구성하는 것이 과제입니다. 결과는 2차원 정수 배열 형태로 반환하며, 유효한 해가 여러 개 존재한다면 그중 어떤 것이든 정답으로 인정됩니다. 반대로 유효한 해가 하나도 없다면 빈 2차원 배열을 반환해야 합니다.
예를 들어 upper = 2, lower = 1, colsum = [1, 1, 1]이 입력으로 주어지면 출력은 [[1, 1, 0], [0, 0, 1]]이 됩니다.
접근 방법
이 문제는 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 각 열의 합(colsum) 값에 따라 다음과 같이 처리합니다.
- colsum[i] = 2인 경우: 해당 열의 위쪽과 아래쪽 요소가 모두 1이어야 하므로, u와 l을 각각 1씩 감소시킵니다. 이때 값이 음수가 되면 유효하지 않은 경우이므로 실패로 표시합니다.
- colsum[i] = 1인 경우: 남은 u와 l 중 더 큰 쪽에 1을 배치하여 두 행의 잔여 합계 균형을 맞춥니다. 두 값이 같다면 어느 쪽에 배치해도 무방하지만, 배치할 행의 남은 값이 0보다 커야 합니다.
- colsum[i] = 0인 경우: 해당 열의 두 요소는 모두 0이며, u와 l에는 어떠한 변화도 일어나지 않습니다.
모든 열을 처리한 후 실패 플래그가 설정되어 있거나 u 또는 l이 0이 아니라면 유효한 행렬을 만들 수 없으므로 빈 배열을 반환합니다.
알고리즘 단계
- flag := true로 설정하고, n := c의 크기로 지정한 뒤 2 × n 크기의 배열 ans를 생성합니다.
- i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
- c[i] = 2이면 u와 l을 각각 1씩 감소시킵니다. u < 0 또는 l < 0이면 flag := false로 설정합니다. 그리고 ans[0][i] = 1, ans[1][i] = 1로 저장합니다.
- c[i] = 1이면 u > l일 때 u를 1 감소시키고 ans[0][i] := 1로 저장하고, u < l일 때 l을 1 감소시키고 ans[1][i] := 1로 저장합니다. u = l인 경우에는 u > 0이면 u를 감소시키고 ans[0][i] := 1로, l > 0이면 l을 감소시키고 ans[1][i] := 1로 저장하며, 둘 다 아니면 flag := false로 설정합니다.
- c[i] = 0이면 별도의 작업 없이 넘어갑니다(두 행 모두 0으로 유지).
- 그 외의 값이 나오면 flag := false로 설정합니다.
- 반복이 끝난 후 flag가 false이거나 u ≠ 0 또는 l ≠ 0이면 빈 배열을 반환합니다.
- 그렇지 않으면 ans를 반환합니다.
예제 코드
아래 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<vector<int>> reconstructMatrix(int u, int l, vector<int>& c) {
bool flag = true;
int n = c.size();
vector < vector <int> > ans(2, vector <int> (n));
for(int i = 0; i < n; i++){
if(c[i] == 2){
u--;
l--;
if(u<0 || l<0)flag = false;
ans[0][i] = 1;
ans[1][i] = 1;
}else if(c[i] == 1){
if(u>l){
u--;
ans[0][i] = 1;
}else if(u<l){
l--;
ans[1][i] = 1;
}else{
if(u>0){
u--;
ans[0][i] = 1;
}else if(l > 0){
l--;
ans[1][i] = 1;
}else
flag = false;
}
}else if(c[i] == 0){
// c[i]가 0이면 두 행의 요소는 모두 0으로 유지
}else{
flag = false;
}
}
if(!flag || u!=0 ||l!=0 )return {};
return ans;
}
};
main(){
vector<int> v = {1,1,1};
Solution ob;
print_vector(ob.reconstructMatrix(2,1,v));
}
입력
2 1 [1,1,1]
출력
[[1, 1, 0],[0, 0, 1]]