[leetcode]Grid Illumination

유의할점

리턴값

lampGrid[dy].erase(dx)

lampGrid[y].insert(x).second

해쉬테이블

풀이

N-Queens 문제와 같다. 다만 hash table을 이용해야한다. 안그러면 TLE를 먹는다.

코드

C++

class Solution {
private:
    unordered_map <int,int> cols, rows, leftDiag, rightDiag;
    unordered_map <int,unordered_set<int>> lampGrid;
    
    int d[3] = {-1,0,1};
    
public:
    vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        vector<int> ans;

        for(int i = 0; i < lamps.size(); i++){
            int y = lamps[i][0];
            int x = lamps[i][1];
            
            if(lampGrid[y].insert(x).second){
                cols[x]++;
                rows[y]++;
                leftDiag[y-x]++;
                rightDiag[y+x]++;
            }
        }
        
        for(int i = 0; i <queries.size(); i++){
            int y = queries[i][0];
            int x = queries[i][1];
            
            int _ = cols[x]||rows[y]||leftDiag[y-x]||rightDiag[y+x] ? 1 : 0;
            //꺼져있으면 켜져있는 램프가 근처에 있을 확률 0%
            if(_){
                for(int j = 0; j < 9; j++){
                    int dy = y + d[j/3];
                    int dx = x + d[j%3];
                    if(lampGrid[dy].erase(dx)){
                        cols[dx]--;
                        rows[dy]--;
                        leftDiag[dy-dx]--;
                        rightDiag[dy+dx]--;
                    }
                }    
            }
            ans.push_back(_);
        }
        
        return ans;
    }
};