22.05.07. 풀었던 문제들

1. 이중우선순위큐

c++에서 set은 bst로 구성되어 있기 때문에(항상 정렬되어 있으며, begin()은 최솟값, end()는 최댓값) multiset을 이용하면 쉽게 풀 수 있다.

​

​

2. 등굣길

간단한 DP로 풀 수 있다. 뭔가 lv2에서 훨씬 어려운 문제를 봤던 것 같은 기분이...

​

​

3. 단어 변환

DFS로 쉽게 구현할 수 있다. 다만, target이 words에 없는 경우를 고려해 주었어야 했다.

​

​

4. 베스트앨범

unordered_map이나 map과, 해당 container 정렬을 통해 쉽게 풀 수 있는 문제.

​

​

5. 여행경로

DFS로 쉽게 구현할 수 있다.

​

​

6. 섬 연결하기

MST 문제이다. prim algorithm으로 구현해도 되고, kruskal algorithm을 사용해도 된다. 다만 kruskal algorithm을 사용하는 경우, disjoint set을 공부해서 union-find 함수를 구현할 수 있어야 한다. 일단 union-find는 잘 기억이 안나니까 prim algorithm으로 구현하고, 나중에 union-find를 공부/정리하면 그때 kruskal로 풀 것이다.

// 섬 연결하기

typedef vector<int> vi;
typedef pair<int, int> pii;

struct pqcmp{
    bool operator()(pii &a, pii &b){
        return a.second > b.second;
    }
};

int solution(int n, vector<vector<int>> costs) {
    // 초기화 단계
    vector<vector<pii>> adjacent(n);
    for(vi v : costs){
        adjacent[v[0]].push_back({v[1], v[2]});
        adjacent[v[1]].push_back({v[0], v[2]});
    }
    
    int cost = 0;
    set<int> s; s.insert(0);
    priority_queue<pii, vector<pii>, pqcmp> pq; // pii.first : 도착 섬, pii.second : 다리 비용
    for(pii p : adjacent[0]){
        pq.push(p);
    }
    while(s.size() < n){
        pii p = pq.top(); pq.pop();
        if(s.find(p.first) == s.end()){ // 연결되지 않았다면 연결
            s.insert(p.first);
            cost += p.second;
            for(pii next_bridge : adjacent[p.first]) pq.push(next_bridge);
        }
    }
    
    return cost;
}

 

7. 단속카메라

greedy하게 풀 수 있다.

접근은 아래 2가지 정도가 가능할 것이다.

1) 진입시점 기준 정렬 - 이 경우 차의 관계는 아래와 같다. 첫 번째 경우에는 윗 차의 나가는 시점에 깔아야 하고, 두 번째 경우는 첫 번째 차의 나가는 시점에, 세 번째 경우는 두 차 모두 깔아줘야 한다. 일관성이 없고, 복잡하다.

2) 나간시점 기준 정렬 - 이 경우 차의 관계는 아래와 같다. 모든 경우, 우선순위가 높은(아래에 있는)차의 나가는 시점에 캠을 깔면 일관적이다.

 

 

// 단속카메라

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

typedef vector<int> vi;

bool cmp(vi &a, vi &b){
    return a[1] < b[1];
}

int solution(vector<vector<int>> routes) {
    // 나간 시점 기준 오름차순 정렬
    sort(routes.begin(), routes.end(), cmp);
    
    // 첫 차가 나가는 시점에 캠을 박음.
    int cam_point = routes[0][1], cnt = 1;
    for(vi v : routes){
        if(v[0] <= cam_point) continue; // 다음 차가 캠에 걸리는 위치라면 어차피 걸리니까 상관없음
        else{ // 캠에 걸리지 않는 위치라면 해당 차의 제일 뒤에 박음.
            cam_point = v[1];
            cnt++;
        }
    }
    
    return cnt;
}