반응형
https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix/
Reconstruct a 2-Row Binary Matrix - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
1. colsum배열을 정렬한다.
: colsum이 크고, 인덱스가 작은순으로 정렬
즉, 1열 내림차순 정렬하되 같으면, 0열이 작은순 정렬
(1) Comparator 오버라이딩
Arrays.sort(newarr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1])
return o1[0] - o2[0];
else
return o2[1] - o1[1];
}
});(2) 람다식을 이용한 오버라이딩
Arrays.sort(newarr, (o1, o2) -> o1[0] == o2[0] ? o1[0] - o2[0] : o2[1] - o1[1]);
2. colsum>0, upper>0 이면 1 아니면 0
colsum>0, lower>0 이면 1 아니면 0
3. 예외처리
: 반복문 이후에도 lower>0, upper>0이거나, colsum[j]>0이면 빈 리스트 리턴
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
//upper, lower, colsum을 이용해 2진 정수 배열로 반환
//0번쨰 행 합계 : 2, 1번째 행합계, 열 합계 : [2,1,1]
//[[1,1,0], [1,0,1]]
//가능하면 일단 넣으면서 반복
int[][] arr= new int[2][colsum.length];
//colsum 내림차순 : 2의 인덱스번호를 먼저 출력
//0, 2, 7, 1, 5, 7, 10, 4, 6, 9 순서
int[][] newarr = new int[colsum.length][2];
for(int i=0;i<colsum.length;i++){
newarr[i][0]=i;
newarr[i][1]=colsum[i];
}
//배열 값이 큰순, 인덱스는 작은 순 정렬
//(1) Comparator 오버라이딩
// Arrays.sort(newarr, new Comparator<int[]>() {
// @Override
// public int compare(int[] o1, int[] o2) {
// if (o1[1] == o2[1])
// return o1[0] - o2[0];
// else
// return o2[1] - o1[1];
// }
// });
//(2) 람다식을 이용해 오버라이딩
Arrays.sort(newarr, (o1, o2) -> o1[0] == o2[0] ? o1[0] - o2[0] : o2[1] - o1[1]);
// for(int i=0;i<arr[0].length;i++){
// for(int j=0;j<2;j++){
// System.out.print(newarr[i][j]+" ");
// }
// System.out.println();
// }
List<List<Integer>> result = new ArrayList<>();
if(colsum==null) return result;
for(int j=0;j<colsum.length;j++){
//System.out.println(j+"번째 열번호: "+newarr[j][0]);
//System.out.println(j+"번째 "+upper+" "+lower+" "+colsum[newarr[j][0]]);
if(upper>0 && colsum[newarr[j][0]]>0) {
// System.out.println(j+" "+1);
arr[0][newarr[j][0]]=1;
upper--;
colsum[newarr[j][0]]--;
}else{
//System.out.println(j+" "+2);
arr[0][newarr[j][0]]=0;
}
if(lower>0 && colsum[newarr[j][0]]>0){
// System.out.println(j+" "+3);
arr[1][newarr[j][0]]=1;
lower--;
colsum[newarr[j][0]]--;
}else{
//System.out.println(j+" "+4);
arr[1][newarr[j][0]]=0;
}
//System.out.println(j+"번째 종료"+upper+" "+lower+" "+colsum[newarr[j][0]]);
if(colsum[newarr[j][0]]>0) return result = new ArrayList<>();
}
if(lower>0 || upper>0) return result = new ArrayList<>();
for(int j=0;j<2;j++){
List<Integer> tmp = new ArrayList<>();
for(int i=0;i<arr[0].length;i++){
tmp.add(arr[j][i]);
}
result.add(tmp);
}
return result;
}
}class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
//이진 매트릭스 재구성
//정렬 이용한 풀이
List<List<Integer>> answer= new ArrayList<>();
int n=colsum.length;
int[][] arr = new int[colsum.length][2];
for(int i=0;i<n;i++){
arr[i][0]=i;
arr[i][1]=colsum[i];
}
//1. colsum 내림차순 정렬
Arrays.sort(arr, (o1, o2)-> o2[1]==o1[1]?o1[0]-o2[0]:o2[1]-o1[1]);
//2.upper와 lower 채우기
int[][] tmp = new int[2][n];
for(int i=0;i<n;i++){
if(upper>0 && arr[i][1]>0) {
arr[i][1]--;
tmp[0][arr[i][0]]++;
upper--;
}
if(lower>0 && arr[i][1]>0) {
arr[i][1]--;
tmp[1][arr[i][0]]++;
lower--;
}
if(arr[i][1]>0) return answer;
}
if(lower>0 || upper>0) return answer;
for(int i=0;i<2;i++){
List<Integer>list = new ArrayList<>();
for(int j=0;j<n;j++){
list.add(tmp[i][j]);
}
answer.add(list);
}
return answer;
}
}
+) 세련된 풀이
1. colsum의 값의 경우 조건분기 : 2, 1, 0
(1) colsum==2 : 모두 1씩 추가
(2) colsum==1 : upper가 lower보다 같거나 크면 1추가, 그외엔 lower에 추가
(3) colsum==0 : 추가하지 않고 넘어간다.
2. colsum의 길이만큼 for문을 돌면서 채운다.
// 2. for
for (int i = 0; i < n; i++) {
if (colsum[i] == 2) {
a1[i] = 1;
a2[i] = 1;
upper--; // 2->1
lower--;// 2->1
} else if (colsum[i] == 1) {
if (upper >= lower) {
a1[i] = 1;
upper--; // 1->0
} else {
a2[i] = 1;
lower--;
}
} else if (colsum[i] == 0) {
a1[i] = 0;
a2[i] = 0;
}
}3. 예외처리 : for문을 돌린 이후에도 (colsum이 남아있거나) -> lower, upper이 0이 아닐 경우에 포함
if(upper !=0 || lower !=0)
return res;
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
// 1. ds
List<List<Integer>> res = new ArrayList<>();
int n = colsum.length; // 3
int[] a1 = new int[n];// 3
int[] a2 = new int[n];
// 2. for
for (int i = 0; i < n; i++) {
if (colsum[i] == 2) {
a1[i] = 1;
a2[i] = 1;
upper--; // 2->1
lower--;// 2->1
} else if (colsum[i] == 1) {
if (upper >= lower) {
a1[i] = 1;
upper--; // 1->0
} else {
a2[i] = 1;
lower--;
}
} else if (colsum[i] == 0) {
a1[i] = 0;
a2[i] = 0;
}
}
if(upper !=0 || lower !=0)
return res;
List<Integer> list = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
for(int k : a1) {
list.add(k);
}
for(int m : a2) {
list2.add(m);
}
res.add(list);
res.add(list2);
return res;
}
}
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
int n=colsum.length;
int[] up = new int[n];
int[] down = new int[n];
List<List<Integer>> answer= new ArrayList<>();
//1. for문으로 조건 분기
for(int i=0;i<n;i++){
if(colsum[i]==2&& lower>0&&upper>0){
up[i]=1;
down[i]=1;
upper--;
lower--;
colsum[i]=0;
}else if(colsum[i]==1){
if(upper>=lower&&upper>0){
up[i]=1;
upper--;
colsum[i]--;
}else if(lower>=upper && lower>0){
down[i]=1;
lower--;
colsum[i]--;
}
}else{
up[i]=0;
down[i]=0;
}
if(colsum[i]>0) return answer;
}
if(lower>0||upper>0) return answer;
List<Integer> list1= new ArrayList<>();
List<Integer> list2= new ArrayList<>();
for(int i=0;i<n;i++){
list1.add(up[i]);
list2.add(down[i]);
}
answer.add(list1);
answer.add(list2);
return answer;
}
}-> 예외처리를 lower,upper로 변경
-> Colsum--할 필요 없이 lower,upper로 예외처리 가능
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
int n=colsum.length;
int[] up = new int[n];
int[] down = new int[n];
List<List<Integer>> answer= new ArrayList<>();
//1. for문으로 조건 분기
for(int i=0;i<n;i++){
if(colsum[i]==2){
up[i]=1;
down[i]=1;
upper--;
lower--;
}else if(colsum[i]==1){
if(upper>=lower){
up[i]=1;
upper--;
}else if(lower>=upper){
down[i]=1;
lower--;
}
}else{
up[i]=0;
down[i]=0;
}
}
if(lower!=0||upper!=0) return answer;
List<Integer> list1= new ArrayList<>();
List<Integer> list2= new ArrayList<>();
for(int i=0;i<n;i++){
list1.add(up[i]);
list2.add(down[i]);
}
answer.add(list1);
answer.add(list2);
return answer;
}
}반응형
'Java > Java 알고리즘 LeetCode' 카테고리의 다른 글
| [LeetCode- Part. 1] 4. 나선형 매트릭스 생성 (0) | 2022.11.04 |
|---|---|
| [LeetCode- Part. 1] 3. 총길이 60초짜리 음악 쌍 (0) | 2022.11.04 |
| [LeetCode- Part. 1] 1. 가장 바깥 괄호제거 (+ StringBuilder, substring) (0) | 2022.11.04 |
| [LeetCode- Ch9. 백트래킹] 4. 핸드폰 숫자의 문자 조합 (0) | 2022.11.04 |
| [LeetCode- Ch9. 백트래킹] 3. 부분집합 (0) | 2022.11.04 |