99코딩

• 3 단계에서 처음 본 최소 신장 트리 문제
• 크루스칼 알고리즘을 통해 해결

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

using namespace std;

// 최소의 비용으로 모든 노드를 연결해야함 > 크루스칼 알고리즘
// 일단 비용 기준으로 정렬 필요
// 이후 부모 노드를 저장한 뒤 노드들을 순회하며 부모 노드가 같은 경우 = 싸이클이 발생하는 경우를 제외하고 다리를 건설

vector<int> parent(101);

// 부모 노드를 찾는 함수
int FindParent(int x) {
    if(parent[x] == x) return x;
    else return parent[x] = FindParent(parent[x]);
}

// 비교자
int cmp(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 비용 기준으로 정렬
    sort(costs.begin(), costs.end(), cmp);
    
    // 부모 노드 저장
    for(int i = 0; i < n; i++)
        parent[i] = i;
    
    for(int i = 0; i < costs.size(); i++) {
        int startNode = FindParent(costs[i][0]);
        int endNode = FindParent(costs[i][1]);
        int cost = costs[i][2];
        
        // 부모 노드가 같지 않다면 싸이클이 생기지 않으므로 다리를 건설 및 부모 노드 갱신
        if(startNode != endNode) {
            answer += cost;
            parent[endNode] = startNode;
        }
    }
    
    return answer;
}

• 완전 탐색 문제
• 단, 경로가 2개 이상일 때 알파벳 순서가 앞서는 경로를 리턴하라 했으므로 정렬하여 알파벳 순서대로 탐색할 수 있도록 하였음

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

using namespace std;

// 무조건 ICN 공항에서 출발
// 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 리턴
// 일단 정렬하면 알파벳 순서로 탐색할 수 있을듯
// 완전 탐색 문제. DFS로 접근

bool dfs(string cur, vector<vector<string>> tickets, vector<string> &answer, vector<bool> &Used, int cnt) {
    // 방문한 공항 저장
    answer.push_back(cur);
    
    // 모든 티켓 사용 완료
    if(tickets.size() == cnt) return true;
    
    // 티켓 배열을 순회하며
    for(int i = 0; i < tickets.size(); i++) {
        // 출발지가 현재 공항이고 사용한적 없는 티켓이라면
        if(tickets[i][0] == cur && !Used[i]) {
            // 사용으로 바꾸고
            Used[i] = true;
            
            // 더 안쪽으로 탐색
            if(dfs(tickets[i][1], tickets, answer, Used, cnt + 1)) return true;
            
            // 위 if 문이 거짓이 되면 모든 항공권 사용 실패이므로 백트래킹
            Used[i] = false;
        }
    }
    
    // 마찬가지로 백트래킹
    answer.pop_back();
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool> Used(tickets.size(), false);
    
    // 정렬
    sort(tickets.begin(), tickets.end());
    
    // dfs
    dfs("ICN", tickets, answer, Used, 0);
    
    return answer;
}

• 그래프에서 bfs/dfs 돌리면 되는 문제

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// 1번에서 가장 멀리 떨어진 노드가 몇 개인지 찾기. 가중치 X
// bfs/dfs 수행해서 가장 멀리 떨어진 노드까지의 거리를 저장하고 해당 거리랑 동일한 값을 갖는 노드를 카운트
// 우선 제공되는 간선 정보를 인접 리스트로 변환
// 이후 1번 노드부터 bfs 시작하며 각 노드에 최단 거리 저장

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<vector<int>> list(n + 1);
    
    // 인접 리스트로 변환
    for(int i = 0; i < edge.size(); i++) {
        list[edge[i][0]].push_back(edge[i][1]);
        list[edge[i][1]].push_back(edge[i][0]);
    }
    
    vector<int> dist(n + 1, -1);
    queue<int> q;
    
    // bfs 수행
    dist[1] = 0;
    q.push(1);
    
    while(!q.empty()) {
        int curNode = q.front();
        q.pop();
        
        for(int nextNode : list[curNode]) {
            if(dist[nextNode] == -1) {
                dist[nextNode] = dist[curNode] + 1;
                q.push(nextNode);
            }
        }
    }
    
    // 가장 큰 거리값 찾기
    int max = *max_element(dist.begin(), dist.end());
    
    // 가장 멀리 떨어진 노드들 찾기
    for(int i = 0; i < dist.size(); i++)
        // 거리가 가장 큰 거리값과 같으면
        if(dist[i] == max) answer++;
    
    return answer;
}

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

// 진열된 모든 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
// 투 포인터 알고리즘

vector<int> solution(vector<string> gems) {
    vector<int> answer;
    unordered_map<string, int> um;
    
    for(int i = 0; i < gems.size(); i++)
        um[gems[i]] = 0;
    
    int start = 0, curGem = 0;
    answer.push_back(0);
    answer.push_back(100001);
    
    for(int end = 0; (end < gems.size()) && start <= end;) {
        // start와 같은 보석이 나오거나 start 지점의 보석과 같은 보석을 여러번 집었다면
        if((end != start && gems[start] == gems[end]) || um[gems[start]] > 1) {
            if(!(--um[gems[start++]])) curGem--;
            continue;
        }
        // end 지점의 보석을 처음 주워본다면
        else if(um[gems[end]]++ == 0) {
            curGem++;
        } 
        
        // 모든 종류의 보석을 집었을 때
        if(curGem == um.size()) {
            // 구간의 길이가 더 짧다면
            if(answer[1] - answer[0] > end - start) {
                answer[0] = start + 1;
                answer[1] = end + 1;
            }
            
            // 해당 구간에서 시작 지점 빼주기
            if(!(--um[gems[start++]])) curGem--;
        }
        
        end++;
    }
    
    return answer;
}

• 해시 문제라 unordered_map으로 접근
• 해당 unorded_map을 벡터에 할당해주고 벡터를 장르별 총합 재생수 기준으로 정렬해준 뒤 각 장르마다 장르 내의 곡들을 재생수 기준으로 정렬(뭐부터 정렬할지 순서는 상관없음)
• 이후 총합 재생수가 높은 장르부터 재생수가 높은 곡 2개를 수록. 단, 장르에 곡이 하나면 한 곡만 수록

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

// 장르 내의 곡들의 재생수 합이 가장 큰 장르부터 장르 내의 곡들을 재생수 순서대로 출력
// 가장 많이 재생된 노래를 두 개씩 모아서 재생
// 해시 문제 unordered_map 사용(key, value 삽입 시 정렬이 필요 없음)

using namespace std;

// 장르별 총합 재생 수 비교자
bool cmpGenre(const pair<string, pair<int, vector<pair<int, int>>>> &a, const pair<string, pair<int, vector<pair<int, int>>>> &b) {
    return a.second.first > b.second.first;
}

// 곡 재생 수 비교자
bool cmpPlay(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, pair<int, vector<pair<int, int>>>> m;
    vector<pair<string, pair<int, vector<pair<int, int>>>>> v;
    
    for(int i = 0; i < genres.size(); i++) {
        m[genres[i]].first += plays[i];
        m[genres[i]].second.push_back({i, plays[i]}); 
    }
    
    v.assign(m.begin(), m.end());
    
    // 장르별 총합 재생수 기준으로 정렬
    sort(v.begin(), v.end(), cmpGenre);
    
    // 각 장르마다 장르 내의 곡들을 재생수 기준으로 정렬
    for(int i = 0; i < v.size(); i++)
        sort(v[i].second.second.begin(), v[i].second.second.end(), cmpPlay);
    
    // 총합 재생수가 높은 장르마다 재생수가 높은 곡 2개씩 수록
    for(int i = 0; i < v.size(); i++) {
        for(int j = 0; j < 2; j++) {
            answer.push_back(v[i].second.second[j].first);
            
            // 장르에 곡이 하나만 있다면 하나만 수록
            if(v[i].second.second.size() == 1) break;
        }
    }
    
    return answer;
}

• 기지국 하나가 커버하는 영역이 W = w x 2 + 1, 전달되지 않는 영역의 크기가 A일 때 
• A % W == 0이면 필요한 기지국의 최소 개수는 A / W, 아니라면 A / W + 1이 됨

• 그림에서 처럼 6,7,8,9 총 4의 크기의 영역이 있고 기지국의 범위가 3이면 4 / 3 + 1 = 2가 됨
• 만약 6, 7, 8 이라면 A / W + 1을 사용하면 3 / 3 + 1 = 2가 되버림
• > A % W == 0이라면 A / W + 1에서 1을 빼줄 필요가 있음

위 공식을 통해 모든 영역 커버를 위한 기지국 설치의 최소 개수를 구하면 되지만 아래 2가지를 추가로 고려해야함

• 첫 번째 기지국이 1번 아파트까지 커버하지 못할 때
• 마지막 기지국이 n번 아파트까지 커버하지 못할 때

#include <iostream>
#include <vector>
using namespace std;

// n = 아파트 개수, stations = 기지국이 설치된 아파트 번호 배열(오름차순 정렬), w = 전파 도달 거리
// 전파가 전달되지 않는 영역에서 모든 영역이 전파를 전달 받으려면 최소 몇 개의 기지국을 설치해야하는가?
// 기지국 하나가 커버할 수 있는 영역은 w x 2 + 1, 이하 W
// 전달되지 않는 영역 하나의 크기를 A라고 할 때 해당 영역을 커버하기 위한 기지국의 최소 개수는
// A / W + 1이 된다. 단, A % W == 0이면 A / W가 된다.
// ex) 커버할 수 있는 영역이 3이고 전달되지 않는 영역 하나의 크기가 3이면 기지국은 하나 필요 => 3 / 3 == 1

int calcStation(int start, int end, int W) {
    int area = end - start + 1;
    
    // 두 기지국이 커버하는 영역이 겹칠 때
    if(area <= 0) return 0;
    // A % W == 0일 때
    else if(area % W == 0) return area / W;
    else return area / W + 1;
}

int solution(int n, vector<int> stations, int w)
{
    int answer = 0;
    int W = w * 2 + 1;
    
    for(int i = 0; i < stations.size(); i++) {
        // 첫 번째 아파트일 때
        if(!i) {
            // 1번 아파트까지 커버한다면 패스
            if((stations[i] - w) == 0) continue;
            // 1번 아파트까지 커버하지 못한다면
            else answer += calcStation(1, stations[i] - w - 1, W);
        }
        else {
            // 영역 계산
            answer += calcStation(stations[i - 1] + w + 1, stations[i] - w - 1, W);
        }
    }
    
    // 마지막 기지국이 n번 아파트까지 커버하지 못할 때
    if(stations[stations.size() - 1] + w < n)
        answer += calcStation(stations[stations.size() - 1] + w + 1, n, W);
    
    return answer;
}

• 핵심은 정렬과 b < a이면 B 안에서 b보다 상대적으로 작은 숫자를 사용해야하는 것
• 전자는 sort를 사용했고 후자는 정렬된 배열에서 A 기준으로 역방향으로 순회하며 b < a면 idxB의 값을 감소시키지 않는 것으로 해결

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

// 두 팀의 순서가 모두 고정된 것이 아니므로 순서는 무시
// 두 배열 모두 정렬한 뒤에 size - 1부터 비교하면 될 듯
// 이렇게하면 a보다 더 큰 숫자 중에 제일 작은 숫자를 뽑거나 할 필요는 없을듯
// b가 a보다 작으면 B 안에서 b보다 상대적으로 작은 숫자를 꺼내야함
// 두 개 배열을 두고 size - 1부터 --해가면서 A가 0에 도달하면 반복을 끝내면 될거 같음

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    
    int idxA = A.size() - 1;
    int idxB = idxA;
    
    // 정렬
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    
    
    for(int i = idxA; idxA >= 0; i--) {
        int numA = A[idxA];
        int numB = B[idxB];
        
        // numB가 numA보다 크면
        if(numB > numA) {
            // answer++하고 B에서 다음으로 큰 숫자를 준비
            answer++;
            idxB--;
        }
        
        // A에서 다음으로 큰 숫자 준비
        idxA--;
    }
    
    return answer;
}

• 일단 정렬
• 첫 번째 차량을 기준으로 해당 차량의 진입 지점보다 멀고 진출 지점보다 가까운 차량을 찾음
• 진입 지점이 진출 지점보다 멀다면 현재 카메라로는 관측이 불가능하므로 answer를 증가시키고
• 진입 지점과 진출 지점을 갱신
• 진입 지점과 진출 지점이 같은 경우에는 갱신 X
• 진출 지점이 가깝다면 해당 지점에 대한 값을 갱신
• 마지막에 무조건 한 대 또는 한 집합이 남으므로 answer = 1로 해주고 시작
• 이를 반복

2레벨에 디펜스 게임?이랑 비슷한 느낌으로 접근하면 됨

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

using namespace std;

// 일단 정렬
// 첫 번째 차량을 기준으로 해당 차량의 진입 지점보다 멀고 진출 지점보다 가까운 차량을 찾음
// 진입 지점이 진출 지점보다 멀다면 현재 카메라로는 관측이 불가능하므로 answer를 증가시키고
// 진입 지점과 진출 지점을 갱신
// 진입 지점과 진출 지점이 같은 경우에는 갱신 X
// 진출 지점이 가깝다면 해당 지점에 대한 값을 갱신
// 마지막에 무조건 한 대 또는 한 집합이 남으므로 answer = 1로 해주고 시작
// 이를 반복

int solution(vector<vector<int>> routes) {
    int answer = 1;
    
    sort(routes.begin(), routes.end());
    
    int enter = routes[0][0];
    int exit = routes[0][1];
    
    for(int i = 1; i < routes.size(); i++) {
        if(routes[i][0] > exit) {
            enter = routes[i][0];
            exit = routes[i][1];
            answer++;
        }
        
        if(routes[i][0] == exit)
            continue;
        
        if(routes[i][1] < exit)
            exit = routes[i][1];
    }
    
    return answer;
}