1488. Avoid Flood in The City

문제: https://leetcode.com/problems/avoid-flood-in-the-city/

Avoid Flood in The City - LeetCode

 

1. 문제 설명

 Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

 

 rains 배열에 들어있는 lake가 두 번 연속되면 flood라는 뜻이다.  rains 배열에서 left -> right로 순차적으로 적용되며, 0이 있는 경우 dry로 비가 온 lake 중 하나를 dry 할 수 있다.

 

n > 0인 경우는 -1이고, n == 0일 때 dry할 lake를 ans 자리에 저장한다.

 

-예시

rains = [1,2,3,4] 

1이 lake의 번호이며,1->2->3->4번 순으로 lake에 비가 온다.  겹치는 번호가 없으므로 [-1, -1, -1, -1]이 반환된다.

 

rains = [1,2,3,2]

 2가 두 개 겹친다.  duplicate라 flood가 된다.

 

rains = [1,2,0,2]

 2가 두 개 겹치는데, 중간에 0이 있다.  0은 임의의 lake를 dry 할 수 있으므로 2번 lake를 dry하면 2번 lake에 비가 한 번 더 내려도 flood되지 않는다.

 

 

2. brute forcing

 

 set과 lower_bound 사용하지 않고 dry를 vector 사용해서 linear search / erase

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n, -1);
        unordered_map<int, int> full;
        vector<int> dry;
        
        for(int i = 0; i < n; i++){
            if(rains[i] == 0){
                dry.push_back(i);
                continue;
            }
            
            if(full.find(rains[i]) != full.end()){
                int idx = -1;
                for(int j = 0; j < dry.size(); j++){
                    if(full[rains[i]] < dry[j]){
                        idx = j;
                        break;
                    }
                }
                
                if(idx == -1){
                    return {};
                }
                ans[dry[idx]] = rains[i];
                dry.erase(dry.begin() + idx);
            }
            full[rains[i]] = i;
        }
        
        for(auto e : dry){
            ans[e] = 1;
        }
        return ans;
    }
};

 

Time complexity: O(N^2)

Space complexity: O(N)

 

3. optimization

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        int n = rains.size();
        vector<int> ans(n, -1);
        unordered_map<int, int> full;
        set<int> dry;
        
        for(int i = 0; i < n; i++){
            if(rains[i] == 0){
                dry.insert(i);
                continue;
            }
            
            if(full.find(rains[i]) != full.end()){
                auto it = dry.lower_bound(full[rains[i]]);
                if(it == dry.end()){
                    return {};
                }
                ans[*it] = rains[i];
                dry.erase(it);
            }
            full[rains[i]] = i;
        }
        
        for(auto e : dry){
            ans[e] = 1;
        }
        return ans;
    }
};

 dry indexes를 찾는데 set과 lower_bound를 사용하면, time coplexity를 O(N^2) -> O(N log N)으로 줄일 수 있다.

 

Time complexity: O(N log N)

Space complexity: O(N)