Leetcode 947 (M)

Most Stones Removed with Same Row or Column

처음 문제를 읽었을때는 인지하지 못했는데, 결국 아래 문제랑 같은것이라는 것을 이해하기까지 시간이 다소 소요되었다. 차이점이라면 문제에서 찾고자 하는 답이 반전되어있다는 것.
547. Number of Provinces

예를들어, 547번 문제의 경우 island의 개수를 세시오라는 것이 명시적으로 나타나있었고, 947번 문제의 경우 최대한 지울 수 있는 point의 숫자를 세시오 라고 나와있었다. 그게 그거인것을 알아차리는게 실력이 늘어나는 과정이 아닐까.

같은 구현이지만 547번을 푸는데는 10분도 안걸렸고, 947번은 TLE가 나오면서 시간이 한참 걸렸다는점.. 반성한다.

---

초기 접근 방법.

명시된 대로, 이떤 point를 삭제할 수 있을지에 대한 고민을 했다.

1. How am I gonna store the points? -> similar to the previous problem(547), used matrix.

2. Select a good starting point and use dfs to erase all the connected points.

여기서의 가장 고민이 되었던 부분은, 어떤 point가 starting point로써 좋은 point일까에 대한 고민을 했다.

1. 우선, 하나의 row혹은 col에 2개 이상의 points를 가지고 있어야 하기 때문에, 각 row와 col에 속해있는 points의 개수를 카운트 하자.
2. 여러 예시를 살펴보다 보니, 적어도 하나의 row, col은 2보다 같거나 크면서, 다른 하나는 최소값이 되는(최소 1)점에서 시작하는 것이, dfs를 통해서 최대한 많은 점들로 연결될 수 있겠다.

---

이 중 잘못된 생각.

1. 문제를 바라보는 관점이 고착화 되어있었다는 점.
2. 반복 조건 설정이 까다로웠다는 점.
3. good starting point에 대한 기준이 명확하지 못했다는 점.

Failed code

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = 1000;
        vector<int> cols(n, 0), rows(n, 0);
        vector<vector<int>> table(1000, vector<int>(1000, 0));
        
        int m = 0;
        for(auto s : stones){
            rows[s[0]]++;
            cols[s[1]]++;
            table[s[0]][s[1]] = 1;
            m = max(m, max(s[0], s[1]));
        }
        m++;
        
        int count = 0;
        			 // *************
        while(true){ // ** Point 2 **
        			 // *************
            if(*max_element(cols.begin(), cols.begin()+m) <= 1 &&
              *max_element(rows.begin(), rows.begin()+m) <= 1) break;
            
            int a = 0, b = 1001;
            int r,c;
            for(int i = 0; i < m; i++){
                for(int j = 0; j < m; j++){
                    if(!table[i][j]) continue;
                    int tmax = max(cols[j], rows[i]);
                    int tmin = min(cols[j], rows[i]);
         			
                    // *************
                    // ** Point 3 **
                    // *************
                    if(tmax >= a && tmin <= b){
                        a = tmax;
                        b = tmin;
                        r = i; c = j;
                    }
                }
            }
            
            // DFS
            
            stack<pair<int, int>> stk;
            stk.push({r, c});
            
            while(!stk.empty()){
                int tr = stk.top().first, tc = stk.top().second;
                stk.pop();
                
                bool dup = false;
                for(int j = 0; j < m; j++){
                    if(table[tr][j] && j != tc){
                        dup = true;
                        stk.push({tr, j});
                    }
                    if(table[j][tc] && j != tr){
                        dup = true;
                        stk.push({j, tc});
                    }
                }
                
                if(dup){
                    count++;
                    table[tr][tc] = 0;
                    rows[tr]--;
                    cols[tc]--;
                }
            }
        }
        
        return count;
    }
};

row든 col이든 어느 한쪽은 많이 겹치면서, 다른쪽은 적게 겹치는 부분이 good starting point일 것이라 생각했지만,

[[1,2],[1,3],[3,3],[3,1],[2,1],[1,0]]

위와 같은 경우, (1,2)이 row = 3, col = 1값을, (2,1)이 row = 2, col = 1 값을 가질 때, starting point 를 (1,2)로 설정하게 되어 문제가 발생하는 등 잘못된 구현이었다.

First accepted code

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        
        unordered_map<int, vector<int>> rows, cols;
        set<int> visited;
        
        for(auto s : stones){
            rows[s[0]].push_back(s[1]);
            cols[s[1]].push_back(s[0]);
        }
        
        int count = 0;
        for(auto s : stones){
            if(!visited.insert(s[0]).second) continue;
            count++;
            
            stack<pair<int,int>> stk;
            stk.push({s[0], s[1]});
            
            while(!stk.empty()){
                int r = stk.top().first;
                int c = stk.top().second;
                stk.pop();
                
                for(auto co : rows[r]){
                    for(auto ro : cols[co]){
                        if(visited.insert(ro).second){
                            stk.push({ro, co});
                        }
                    }
                }
            }
            
        }
        
        return n-count;
        
    }
};

DFS로 섬의 개수를 찾는 574번 방법과 동일한 방법을 사용해서, 그 값을 point에서 제거해주는 방식으로 간단하게 해결.

Better code

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        for (int i = 0; i < stones.size(); ++i)
            uni(stones[i][0], ~stones[i][1]);
        return stones.size() - islands;
    }

    unordered_map<int, int> f;
    int islands = 0;

    int find(int x) {
        if (!f.count(x)) f[x] = x, islands++;
        if (x != f[x]) f[x] = find(f[x]);
        return f[x];
    }

    void uni(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) f[x] = y, islands--;
    }
        
};

Union-find를 사용한 방법.

가장 빠른 속도와, 적은 메모리 사용으로 우수한 성능을 보여줬다.
아직 Path compression을 사용하는 부분이 tricky함.

TIL

1. set에 대한 insert함수의 second return값은 inserting을 성공 하였는지, 실패하였는지를 나타낸다. 일일이 set에 key값이 들어있는지 확인하는 과정을 생략 할 수 있는 좋은 방법.

2. 574번 문제에서는 matrix형태로 graph를 제공했기에, for문으로 row가 0 부터 n-1까지 iterate하면서 이미 방문한 row인 경우 skip하는 식으로 했었다. 그런데 이번에는 points가 주어졌기 때문에, 이 points로 matrix를 만들고서 위와 동일한 방법을 적용할것인가? 에 대한 고민을 했는데, 그렇지 않고 그냥 visited된 col or row를 set으로 check하면서 모든 point들을 돌아보는 방식을 구현할 수 있을 것이다.

3. row, col을 한번에 표현할 수 있는 방법으로 단순히 특정 숫자를 하나에 곱해서 추출하는 방식을 선택했는데, ~연산을 통해서 0->-1, 1->-2로 바꾸는 2's compliment 를 사용하는 것이 가능하다.