[LeetCode- Part. 1] 2. 2행N열 재구성 (+ 2차원 배열 정렬)

https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix/

Reconstruct a 2-Row Binary Matrix - LeetCode

 

 

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;
    }
}