23.09.24. 풀었던 문제들

Programmers Lv. 3 보석 쇼핑, 19분

 two-pointer를 활용하면 되는 문제. 유의할 점은 start와 end 사이에 있는 보석 개수를 세야 하는데, map으로 숫자를 세면 count에 O(보석 개수)만큼의 시간이 걸리고, multiset을 쓰면 identical한 보석 개수를 셀 수 없기 때문에 map과 set을 같이 썼다.

set<string> cur_gems;
int num;
map<string, int> cur_gem_count;

bool isContainAll(){
    return cur_gems.size() == num;
}

void insert(string gem){
    cur_gem_count[gem]++;
    cur_gems.insert(gem);
}

void erase(string gem){
    cur_gem_count[gem]--;
    if(cur_gem_count[gem] == 0) cur_gems.erase(gem);
}

vector<int> solution(vector<string> gems) {
    set<string> s;
    for(string gem : gems){
        s.insert(gem);
        cur_gem_count[gem] = 0;
    }
    num = s.size();

    int start = 0, end = 0;
    insert(gems[start]);
    vector<int> answer = {-1, 100001};
    while(start < gems.size() && end < gems.size()){
        if(start > end){
            end = start;
            continue;
        }

        if(isContainAll()){
            if(answer[1] - answer[0] + 1 > end - start + 1){
                answer[1] = end + 1;
                answer[0] = start + 1;
            }
            erase(gems[start]);
            start++;
        }
        else{
            end++;
            if(end < gems.size()) insert(gems[end]);
        }


    }


    return answer;
}

 

시간복잡도

 set/map에 insert/pop 시 O(logn)이고, two-pointer가 순회하는 데 걸리는 시간은 O(n)이므로, O(nlogn)이다.

 

 

 

Programmers Lv. 3 가장 먼 노드, 8분

 weight가 1보다 크다면 dijkstra를 써야 하지만, 모든 edge weight를 1로 두기 때문에 BFS를 쓰면 되는 문제. 뭐.. 별 것 없다.

typedef pair<int, int> pii; // .first : to, .second : dist

queue<pii> q;
vector<vector<int>> edges;

int solution(int n, vector<vector<int>> edge) {
    vector<int> visited(n+1, -1);
    edges.resize(n+1);
    for(vector<int> e : edge){
        int from = e[0], to = e[1];
        edges[from].push_back(to);
        edges[to].push_back(from);
    }

    q.push({1, 0});
    visited[1] = 0;

    int max_value = -1;
    while(!q.empty()){
        pii front = q.front(); q.pop();

        for(int next : edges[front.first]){
            if(visited[next] != -1) continue;

            visited[next] = front.second + 1;
            q.push({next, front.second + 1});
            max_value = max(max_value, visited[next]);
        }
    }

    int answer = 0;
    for(int v : visited) if(v == max_value) answer++;
    return answer;
}

 

시간복잡도

 BFS는 O(V+E)

 

 

 

Programmers Lv. 3 섬 연결하기, 7분 30초

 MST를 구성하는 문제. 예전에 포스팅도 했었다. union-find를 쓰는 kruskal과 pq를 쓰는 prim 2가지 방법이 있는데, 

typedef pair<int, int> pii;

struct cmp{
    bool operator()(pii &a, pii &b){
        if(a.second == b.second) return a.first > b.first;
        return a.second > b.second;
    }
};

priority_queue<pii, vector<pii>, cmp> pq;
vector<vector<pii>> edges;
vector<int> visited;

int solution(int n, vector<vector<int>> costs) {
    edges.resize(n);
    visited.resize(n);
    fill(visited.begin(), visited.end(), false);
    for(vector<int> cost : costs){
        int from = cost[0], to = cost[1], weight = cost[2];
        edges[from].push_back({to, weight});
        edges[to].push_back({from, weight});
    }

    // prim
    visited[0] = true;
    for(pii e : edges[0]) pq.push(e);

    int answer = 0;
    while(!pq.empty()){
        pii front = pq.top(); pq.pop();
        if(visited[front.first]) continue;

        visited[front.first] = true;
        answer += front.second;
        for(pii e : edges[front.first]) pq.push(e);
    }

    return answer;
}

 

시간복잡도

 prim의 경우 O(ElogV)이지만 이 코드는 O(ElogE)이다. 기존 prim은 set을 사용해서 visited를 판별하기 때문에 O(ElogV)이다. 반면 여기서는 모든 edge에 대해 edge를 뽑는 for문이 1번씩 수행되므로 O(E), 그리고 pq에 모든 edge가 들어가므로 O(ElogE)이다.