99코딩

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

using namespace std;

/*
[x, y, a, b]
x, y는 기둥 또는 보를 설치할 교차점의 좌표
a = 0은 기둥, 1은 보
b = 0은 삭제, 1은 설치
구조물은 좌표 기준 보는 오른쪽, 기둥은 위쪽으로 설치

설치 조건
기둥은 바닥 위, 보의 한쪽 끝 부분, 기둥 위에 있어야함
보는 한쪽 끝 부분이 기둥 위에 있거나 양쪽 끝 부분이 다른 보와 연결되어 있어야함
 + 구조물이 겹치도록 설치되는 경우는 주어지지 않음

삭제 조건
삭제한 후에도 남은 기둥과 보들이 설치 조건을 만족한 상태여야 삭제 가능
 + 없는 기둥을 삭제하는 경우는 주어지지 않음
 
정렬 조건
x 좌표 기준 오름차순 정렬, x 좌표가 같으면 y 좌표 기준 오름차순 정렬
x, y 동일 시 기둥이 보보다 앞으로
*/

int N;
bool Pillar[101][101];
bool Beam[101][101];

struct STRUCTURE {
    int x;
    int y;
    int type;
    bool isDeleted;
};

vector<STRUCTURE> list;

// 기둥 설치 가능 여부
bool checkDeployPillar(int x, int y) {
    // 바닥이면
    if(x == N) return true;
    // 보의 오른쪽에 설치할 때
    if(Beam[x][y - 1] && y >= 1) return true;
    // 보의 왼쪽에 설치할 때
    if(Beam[x][y]) return true;
    // 기둥 위에 설치할 때
    if(Pillar[x + 1][y]) return true;
    
    return false;
}

// 보 설치 가능 여부
bool checkDeployBeam(int x, int y) {
    // 왼쪽 끝에 기둥이 있을 때
    if(Pillar[x + 1][y]) return true;
    // 오른쪽 끝에 기둥이 있을 때
    if(Pillar[x + 1][y + 1] && y + 1 <= N) return true;
    // 양쪽 끝에 보가 있을 때
    if(Beam[x][y - 1] && Beam[x][y + 1]) return true;
    
    return false;
}

// 기둥 삭제 가능 여부
void DeletePillar(int x, int y) {
    int idx = 0;
    // 해당 기둥이 설치되지 않음을 가정
    Pillar[x][y] = false;
    
    for(int i = 0; i < list.size(); i++) {
        int curX = list[i].x;
        int curY = list[i].y;
        int Type = list[i].type;
        
        // 현재 구조물이 삭제하려는 기둥과 같다면
        if(x == curX && y == curY && Type == 0) {
            idx = i;
            continue;
        }
        
        // 이미 삭제된 구조물이면
        if(list[i].isDeleted) 
            continue;
        
        // 리스트에 있는 기둥 중 설치가 불가능한 기둥이 나온다면
        if(Type == 0 && checkDeployPillar(curX, curY) == false) {
            Pillar[x][y] = true;
            return;
        }
        
        // 리스트에 있는 보 중 설치가 불가능한 보가 나온다면
        if(Type == 1 && checkDeployBeam(curX, curY) == false) {
            Pillar[x][y] = true;
            return;
        }
    }
    
    list[idx].isDeleted = true;
}

// 보 삭제 가능 여부
void DeleteBeam(int x, int y) {
    int idx = 0;
    // 해당 보가 설치되지 않았음을 가정
    Beam[x][y] = false;
    
    for(int i = 0; i < list.size(); i++) {
        int curX = list[i].x;
        int curY = list[i].y;
        int Type = list[i].type;
        
        // 현재 구조물이 삭제하려는 보과 같다면
        if(x == curX && y == curY && Type == 1) {
            idx = i;
            continue;
        }
        
        // 이미 삭제된 구조물이면
        if(list[i].isDeleted) 
            continue;
        
        // 리스트에 있는 기둥 중 설치가 불가능한 보가 나온다면
        if(Type == 0 && !checkDeployPillar(curX, curY)) {
            Beam[x][y] = true;
            return;
        }
        
        // 리스트에 있는 보 중 설치가 불가능한 보가 나온다면
        if(Type == 1 && !checkDeployBeam(curX, curY)) {
            Beam[x][y] = true;
            return;
        }
    }
    
    list[idx].isDeleted = true;
}

bool cmp(STRUCTURE a, STRUCTURE b) {
    if(a.y <= b.y) {
        if(a.y == b.y) {
            if(a.x >= b.x) {
                if(a.x == b.x) {
                    if(a.type < b.type) {
                        return true;
                    }
                    return false;
                }
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}

vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    N = n;
    vector<vector<int>> answer;
    
    for(int i = 0; i < build_frame.size(); i++) {
        int x = n - build_frame[i][1];
        int y = build_frame[i][0];
        int type = build_frame[i][2];
        int deploy = build_frame[i][3];
        
        // 설치일 때
        if(deploy == 1) {
            // 기둥
            if(type == 0 && checkDeployPillar(x, y)) {
                list.push_back({x, y, type, false});
                Pillar[x][y] = true;
            }
            // 보
            if(type == 1 && checkDeployBeam(x, y)) {
                list.push_back({x, y, type, false});
                Beam[x][y] = true;
            }
        }
        // 제거일 때
        else {
            // 기둥
            if(type == 0) {
                DeletePillar(x, y);
            }
            // 보
            if(type == 1) {
                DeleteBeam(x, y);
            }
        }
    }
    
    sort(list.begin(), list.end(), cmp);
    
    for(int i = 0; i < list.size(); i++) {
        if(list[i].isDeleted)
            continue;
        
        answer.push_back({list[i].y, N - list[i].x, list[i].type});
    }
    
    return answer;
}

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

using namespace std;

/*
순열을 통해 조합을 만들고 해당 조합에서 banned_id의 크기만큼 아이디를 선택하여 조건을 만족하는지 체크
이후 조건을 만족하는 아이디들의 크기가 banned_id와 같으면 set에 저장(중복 제거)
*/

set<string> s;

// 조건 체크
// a가 banned_id, b가 조건 체크할 id
bool isBanned(string a, string b) {
    if(a.length() == b.length()) {
        for(int i = 0; i < a.length(); i++) {
            if(a[i] == b[i] || a[i] == '*')
                continue;
            else 
                return false;
        }
    }
    else
        return false;
    
    return true;
}

int solution(vector<string> user_id, vector<string> banned_id) {
    // 순열 사용을 위해 정렬
    sort(user_id.begin(), user_id.end());
    
    do {
        vector<string> v;
        string str = "";
        
        // 조건 체크
        for(int i = 0; i < banned_id.size(); i++)
            if(isBanned(banned_id[i], user_id[i]))
                v.push_back(user_id[i]);
        
        // banned_id.size()만큼의 id가 조건을 충족했다면
        if(banned_id.size() == v.size()) {
            // 순서가 관계 없어야하기 때문에 정렬
            sort(v.begin(), v.end());
            
            for(auto& e : v)
                str += e;
            
            s.insert(str);
        }
        
    } while(next_permutation(user_id.begin(), user_id.end()));
    
    return s.size();
}

• 이분탐색 문제
• 데이터 타입에 주의하자

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

using namespace std;

/*
이분 탐색
최소 시간을 1명을 1분으로 끝낸다고 가정하면 1
최대 시간은 가장 오래 걸리는 심사원에게 모든 인원이 심사를 받으러 갔을 때
위 둘을 각각 left, right로 하여 이분탐색 직행
mid를 각 심사위원이 심사하는데 걸리는 시간으로 나눈 값을 더하면 mid분일 때 심사할 수 있는 인원이 나옴
mid분에서 처리할 수 있는 인원이 n보다 크면 right를 mid - 1로 하고 작으면 left를 mid + 1로 해서 계속 탐색
left == right가 되면 탐색을 중단
*/

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    // times 배열 정렬
    sort(times.begin(), times.end());
    
    // 최소 시간
    long long left = 1;
    // 최대 시간, 데이터 타입에 주의
    long long right = n * (long long)times.back();
    
    while(left <= right) {
        long long mid = (left + right) / 2;
        
        // mid분에서 심사를 끝낼 수 있는 인원 수
        long long cnt = 0;
        
        for(int i = 0; i < times.size(); i++)
            cnt += mid / (long long)times[i];
        
        // n보다 많거나 같은 수의 인원의 심사를 끝낼 수 있다면
        if(cnt >= n) {
            right = mid - 1;
            answer = mid;
        }
        // n 보다 적은 수의 인원의 심사를 끝낼 수 있다면
        else {
            left = mid + 1;
        }
    }
    
    
    return answer;
}

• dp 문제
• 전체 수열에 펄스 수열을 곱해서 나올 수 있는 연속 펄스 수열의 종류는 두 가지 뿐
• 두 종류의 수열을 만든 후 두 수열을 돌면서 연속된 구간의 합이 최대가 되는 곳을 찾아야함
• 점화식이 2번째 요소부터 시작인데 sequence의 사이즈는 최소 1일 수 있어서 sequence의 사이즈가 1인 경우를 고려해야함

#include <string>
#include <vector>

using namespace std;

// 펄스 수열은 [1, -1, 1...] 또는 [-1, 1, -1...], 즉 1 또는 -1로 시작
// 전체 수열에 펄스를 곱해서 나올 수 있는 수열은 두 가지 뿐
// 두 종류의 수열을 만든 후 두 수열을 돌면서 연속된 구간의 합이 최대가 되는 곳을 찾아야함
// 점화식으로 나타내면 dp[i] = max(dp[i - 1] + sequence[i], sequence[i])

// dp가 2번째 요소부터 시작이다보니 주어진 수열의 사이즈가 1인 경우도 따로 고려해야함
// 이거 안해서 2번 테스트 케이스 틀림

// 연속 펄스 수열 만들기
vector<int> multiplyPurse(vector<int> sequence, int pulse) {
    for(int i = 0; i < sequence.size(); i++) {
        sequence[i] = sequence[i] * pulse;
        pulse *= -1;
    }
    
    return sequence;
}

long long solution(vector<int> sequence) {
    long long answer = INT32_MIN;
    int size = sequence.size();
    
    // 각각 1과 -1로 시작하는 펄스 수열을 곱한 연속 펄스 수열 만들기
    vector<int> sequence1 = multiplyPurse(sequence, 1);
    vector<int> sequence2 = multiplyPurse(sequence, -1);
    
    long long dp1[size];
    long long dp2[size];
    
    dp1[0] = sequence1[0];
    dp2[0] = sequence2[0];
    
    // 이거 안해줘서 틀림
    if(size == 1) {
        answer = max(dp1[0], dp2[0]);
        return answer;
    }
    
    // dp 수행
    for(int i = 1; i < size; i++) {
        dp1[i] = max(dp1[i-1] + (long long)sequence1[i], (long long)sequence1[i]);
        answer = max(dp1[i], answer);
    }
    
    for(int i = 1; i < size; i++) {
        dp2[i] = max(dp2[i-1] + (long long)sequence2[i], (long long)sequence2[i]);
        answer = max(dp2[i], answer);
    }
    
    return answer;
}

• 콘이 최대한 늦게 버스 정류장에 도착하여 사무실로 가려면 마지막 버스를 마지막으로 타면 됨

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

using namespace std;

// 셔틀은 9시부터 t분 간격으로 n번 도착
// 셔틀이 도착한 순간에 자리가 남고 그 순간에 도착한 크루가 있으면 탑승 가능
// 콘은 최대한 늦게, 그러니까 마지막 버스를 타야함
// 일단 시:분 형태로 주어지는 문자열을 시 * 60 + 분 형태의 int형으로 변환

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    int time = 0;
    
    vector<int> timeTable;
    
    for(auto& time : timetable)
        timeTable.push_back(stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3, 2)));
    
    sort(timeTable.begin(), timeTable.end());
    
    int cnt = 0;
    int arrivalTime = 540;
    
    for(int i = 1; i <= n; i++) {
        int cntInBus = 0;
        
        while(cntInBus < m && cnt < timeTable.size()) {
            if(timeTable[cnt] <= arrivalTime) {
                cntInBus++;
                cnt++;
            }
            else 
                break;
        }
        
        // 마지막 버스일 때
        if(i == n) {
            // 자리가 남으면 버스 도착시간에 맞춰 오면 됨
            if(cntInBus < m)
                time = arrivalTime;
            // 자리가 안남으면 마지막 사람보다 1분 일찍 오면 됨
            else
                time = timeTable[cnt - 1] - 1;
        }
        
        arrivalTime += t;
    }
    
    int hour = time / 60;
    int minute = time % 60;
    
    if(hour < 10)
        answer = "0" + to_string(hour) + ":";
    else 
        answer = to_string(hour) + ":";
    
    if(minute < 10)
        answer += "0" + to_string(minute);
    else
        answer += to_string(minute);
    
    return answer;
}

• 해당 요청시점에서 들어온 작업 중 소요 시간이 짧은 작업들부터 처리하는 것이 관건
• 작업 배열을 요청 시점 기준으로 오름차순 정렬하고 이후 우선순위 큐에 소요 시간 기준으로 오름차순 정렬
• 이후 모든 작업을 완료할 때까지 작업 수행

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

using namespace std;

// 소요 시간이 짧은 것부터 처리하는 것이 평균을 줄이는 방법
// 일단 jobs 배열을 오름차순으로 정렬하고 우선순위 큐에 소요 시간을 기준으로 오름차순 정렬하면 될듯

struct cmp {
    bool operator()(vector<int> a, vector<int> b) {
        return a[1] > b[1];
    }
};

int solution(vector<vector<int>> jobs) {
    // 각각 총 소요시간, 현재까지의 소요시간, 작업 카운트
    int totalCost = 0, curCost = 0, cnt = 0;
    
    priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
    
    // 정렬
    sort(jobs.begin(), jobs.end()); 
    
    // 작업이 끝나지 않은 동안
    while(cnt < jobs.size() || !pq.empty()) {
        
        // 요청 시간이 현재까지의 소요 시간보다 작으면
        if(cnt < jobs.size() && jobs[cnt][0] <= curCost) {
            pq.push(jobs[cnt]); 
            cnt++;
            continue;
        }
        
        // 우선순위 큐에 수행할 작업이 들어있다면
        if(!pq.empty()) {
            curCost += pq.top()[1];
            totalCost += curCost - pq.top()[0];
            pq.pop();
        }
        // 작업은 남았는데 현재 시간에 우선순위 큐에 들어있는 작업이 없다면
        else {
            curCost = jobs[cnt][0];
        }
    }
    
    return totalCost / jobs.size();
}

• 최단거리 문제
• bfs로 해결
• 현재 길의 정보에만 방향성을 추가하면 될 줄 알았으나 25번 케이스가 오답이 나와서 찾아보니cost 배열 자체에도 방향성을 저장할 필요가 있다고 해서 적용하니 해결됨

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

using namespace std;

// bfs를 수행하면서 전달하는 정보에 방향을 추가하면 될 것 같음

struct INFO {
    int x;
    int y;
    int cost;
    int dir;
};

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0, -1, 0};

int solution(vector<vector<int>> board) {
    int answer = INT32_MAX;
    
    int cost[4][26][26];
    
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 26; j++)
            for(int k = 0; k < 26; k++)
                cost[i][j][k] = INT32_MAX;
    
    queue<INFO> q;
    q.push({0, 0, 0, 0});
    cost[0][0][0] = 0;
    
    q.push({0, 0, 0, 1});
    cost[1][0][0] = 0;
    
    // bfs 수행
    while(!q.empty()) {
        INFO curINFO = q.front();
        q.pop();
        
        if(curINFO.x == board.size() - 1 && curINFO.y == board.size() - 1) {
            answer = min(answer, curINFO.cost);
            continue;
        }
        
        for(int i = 0; i < 4; i++) {
            int nx = curINFO.x + dirX[i];
            int ny = curINFO.y + dirY[i];
            
            if(nx >= 0 && nx < board.size() && ny >= 0 && ny < board.size()) {
                if(board[nx][ny] == 1) continue;
                
                int nCost;
                if(curINFO.dir == i) nCost = curINFO.cost + 100;
                else nCost = curINFO.cost + 600;

                if(nCost <= cost[i][nx][ny]) {
                    cost[i][nx][ny] = nCost;
                    INFO nextINFO = {nx, ny, nCost, i};
                    q.push(nextINFO);
                }
            }
        }
    }
    
    return answer;
}

• 간단한 bfs/dfs 문제
• roads를 각 노드에 대한 인접 리스트로 만들어서 bfs를 수행하면 됨

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

// 그래프 문제
// 각 노드별 인접 리스트를 만들어서 bfs 돌리면 될듯

using namespace std;

int bfs(int startNode, int destination, vector<vector<int>> &list) {
    queue<pair<int, int>> q;
    bool isVisited[100001] = {false};
    int dist = INT32_MAX;
    
    q.push({startNode, 0});
    isVisited[startNode] = true;
    
    while(!q.empty()) {
        int curNode = q.front().first;
        int movedDist = q.front().second;
        q.pop();
        
        if(curNode == destination) {
            dist = min(dist, movedDist);
        } 
        
        for(int i = 0; i < list[curNode].size(); i++) {
            if(!isVisited[list[curNode][i]]) {
                isVisited[list[curNode][i]] = true;
                q.push({list[curNode][i], movedDist + 1});
            }
        }
    }
    
    return dist;
}

vector<int> solution(int n, vector<vector<int>> roads, vector<int> sources, int destination) {
    vector<int> answer;
    vector<vector<int>> list(n + 1);
    
    // 리스트 생성
    for(int i = 0; i < roads.size(); i++) {
        list[roads[i][0]].push_back(roads[i][1]);
        list[roads[i][1]].push_back(roads[i][0]);
    }
    
    // 각 부대원 별로 bfs 수행
    for(int i = 0; i < sources.size(); i++) {
        // 이미 목적지에 위치해 있으면
        if(sources[i] == destination) {
            answer.push_back(0);
            continue;
        }
        
        int result = bfs(sources[i], destination, list);
        
        if(result == INT32_MAX) answer.push_back(-1);
        else answer.push_back(result);
    }
    
    return answer;
}