IT로 세상을 이롭게

<문제> 

leetcode.com/problems/set-matrix-zeroes/

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

• A straight forward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

<풀이>

- 가장 쉽게 접근하는 방법은 원본과 똑같은 공간을 하나 더 만들어서 순차적으로 탐색하는 방법이다. 이 경우 공간복잡도가 O(mn)이며 문제에서는 권장하지 않는 방법이다.

- 그 다음의 접근하는 방법은 0이 있는 위치를 기억하는 것이다. row 와 column 을 각각 체크할 수 있는 공간을 만든다면 공간복잡도는 O(m) + O(n)이 된다. 간단히 살펴보면 다음과 같다.

// o(m+n)
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int[] rowCheck = new int[n];
        int[] columnCheck = new int[m];

        for(int i=0; i<n; i++){
            for(int j=0; j< m ; j++){
                if(matrix[i][j] == 0) {rowCheck[i]=1; columnCheck[j]=1;}
            }
        }

        for(int i=0; i<n; i++){
            if(rowCheck[i]==1){
                for(int j=0;j<m;j++){
                    matrix[i][j]=0;
                }
            }
        }
        for(int j=0; j<m ; j++){
            if(columnCheck[j]==1){
                for( int i=0; i<n; i++){
                    matrix[i][j]=0;
                }
            }
        }
    }

- 최초 입력받은 matrix에서 row와 column에 '0' 인 위치를 기억해두었다가 해당 위치의 값을 변경하는 방식이다.

- 그렇다면 문제에서 제안하는 Best Solution은 무엇일까? 제공되는 힌트를 보면

# Hint 1 (추가 메모리 공간이 없도록 manipulate)

If any cell of the matrix has a zero we can record its row and column number using additional memory. But if you don't want to use extra memory then you can manipulate the array instead. i.e. simulating exactly what the question says.

# Hint 2 (불일치가 일어나지 않도록 market관리)

Setting cell values to zero on the fly while iterating might lead to discrepancies. What if you use some other integer value as your marker? There is still a better approach for this problem with 0(1) space.

# Hint 3 (row/columns를 분리해서 생각하기 보다는 하나로 가져갈수 있는방법)

We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.

# Hint 4 (! 모든 행과열의 첫번째 셀을 flag로 사용할 수 있다.)

We can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero.

이와 같은 힌트를 동해 다음과 같이 접근해보자.

1. 첫번째 행과 첫번째 열을 우리가 위에서 마련했던 O(m+n) 의 공간으로 사용한다.

2. 단 이 때 기존에 세팅되어 있던 값을 보존해야 한다. 이후 matrix의 값을 "0"을 치환하는 과정에서 첫번째 행과 열의 값을 참조해야 하는데 값이 구분되지 않아서 불일치가 일어날 수 있다. 

3. 따라서 최초 첫번째 행과 열에 있던 값을 기억하여 나중에 일괄처리 할 수 있도록 하며, 2번의 변환과정의 범위에서 첫번째 행과 열은 제외해야 한다.

// constant
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        boolean isFirstColumnHasZero=false;
        boolean isFirstRowHasZero=false;

        //1. first column
        for(int i=0; i<m; i++){
            if(matrix[i][0] == 0){
                isFirstColumnHasZero=true;
                break;
            }
        }
        //2. first row
        for(int j=0; j<n; j++){
            if(matrix[0][j] == 0){
                isFirstRowHasZero=true;
                break;
            }
        }
        //3. check 0
        for(int i=1; i<m ; i++){
            for(int j=1; j<n ; j++){
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        //4. Process 0
        for(int i=1; i<m ; i++){
            for(int j=1; j<n ; j++){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j]=0;
                }
            }
        }
        //5. first row
        if(isFirstRowHasZero){
            for(int j=0;j<n;j++){
                matrix[0][j]=0;
            }
        }
        //6. first column
        if(isFirstColumnHasZero){
            for(int i=0; i<m; i++){
                matrix[i][0]=0;
            }
        }
    }

<참조>

leetcode.com/problems/set-matrix-zeroes/

<문제>

https://leetcode.com/problems/reorganize-string/

- 같은 문자가 인접하지 않도록 재배열하는 문제입니다.

<wrong>

- 나열되어 있는 문자열을 하나씩 꺼내어 만들면서 인접한지 체크하는 방법은 시간복잡도를 초과하게 됩니다.

<접근법>

- s : [1~500]

- 영어 소문자 26개가 나타날 수 있습니다.

- 같은 문자가 인접하지 않으려면 각 문자를 돌아가면서 선택하여 결과 문자열을 만드는 것으로 생각할 수 있습니다.

e.g) aabb -> abab,   aaabbc -> acabab / ababac

- 그렇다면 가장 자주 나타나는 문자를 먼저 사용하는 것이 유리하겠습니다.

- 같은 빈도수라면 우선순위를 정해야 겠습니다. (영어일 경우 알파벳순이 일반적입니다.)

<Key point>

- 가장 자주 나타나는 문자를 알기 위해서는 먼저 각 문자의 count를 구해야 합니다.

 시간복잡도 O(s) : s가 500이므로 충분합니다.

- 자주 나타나는 문자를 먼저 사용하기 위해서는 MaxHeap의 자료구조가 필요합니다.

 시간복잡도 O(log(x)) : 문자의 종류는 26가지 입니다. (영어소문자)

- MaxHeap에서 2개의 문자(X,Y) 를 꺼낸뒤 결과문자열을 만듭니다.

- 꺼낸 문자의 Count를 1 감소시키고 다시 넣습니다.

<boundary>

- MaxHeap에 문자가 1개만 남은경우는 ?? (현재 남은 문자 Z)

a) 해당 문자의 count가 1이상이라면 : 이후 만들어지는 문자열은 같은 문자가 인접할 수 밖에 없습니다. -> 불가능

b) 해당 문자의 count가 1이라면 :  이전 결과 문자열을 만들때 MaxHeap에서 꺼낸 문자가 X,Y 라고 하고 Y!=Z 이면 가능

 1. Y=Z 가 되는 케이스

 Y=Z 이라면 꺼낼당시 Y:2 이며 -> X:1 , Y:2 인 경우는 MaxHeap의 정의에 모순이 됨 

                                            또한 X:2이상 , Y:2 인 경우는 MaxHeap 문자가 1개 남는다는 가정과 모순이 됨

 2. 따라서 Y!=Z 인 경우만 가능함

 Y!=Z 이라면 꺼낼당시 Y:1 이며 -> Z(1) 관계없이 성립

<solution>

import java.util.Comparator;
import java.util.PriorityQueue;

public class ReorganizeString {

    public class Info{
        public char key;
        public int count;

        public Info(char key, int count){
            this.key=key;
            this.count=count;
        }
    }

    public static void main(String[] args){
        ReorganizeString module = new ReorganizeString();
        module.reorganizeString("aab");
    }
    public String reorganizeString(String S) {
        String ret = "";
        int[] array = new int[26];
        for(int i = 0; i < S.length(); i++){
            array[S.charAt(i) - 'a']++;
        }
        PriorityQueue<Info> pq = new PriorityQueue<Info>(new Comparator<Info>() {
            @Override
            public int compare(Info o1, Info o2) {
                return (o1.count - o2.count)* - 1;
            }
        });
        for(int i = 0; i < 26; i++){
            if(array[i] > 0 ) {
                pq.add( new Info((char)(i+'a'), array[i]) );
            }
        }

        while(!pq.isEmpty()){
            if(pq.size() > 1){
                Info a = pq.poll();
                Info b = pq.poll();
                ret += a.key;
                ret += b.key;

                a.count--;
                b.count--;

                if(a.count > 0 ){
                    pq.add(a);
                }
                if(b.count > 0 ){
                    pq.add(b);
                }
            }else{
                Info a = pq.poll();
                if(a.count ==1){
                    ret +=a.key;
                }else{
                    ret="";
                }
            }
        }
        return ret;
    }
}

<참고>

https://github.com/ggthename