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;
}