99코딩

• data를 조건에 따라 정렬
• data의 row_begin <= i <= row_end에 3번을 수행한 값을 따로 배열에 저장
• 해당 배열의 값들을 누적하여 birwise XOR 연산 수행

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

using namespace std;

int idx;

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

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    idx = col - 1;
    
    // data를 조건에 따라 정렬
    sort(data.begin(), data.end(), cmp);
    vector<int> s;
    
    // row_begin <= i <= row_end
    for(int i = row_begin - 1; i <= row_end - 1; i++) {
        int num = 0;
        
        // S_i는 i 번째 행의 튜플에 대해 각 컬럼의 값을 i로 나눈 나머지들의 합
        for(int j = 0; j < data[i].size(); j++)
            num += data[i][j] % (i + 1);
        
        s.push_back(num);
    }
    
    answer = s[0];
    
    // 해시 값은 s 배열의 모든 값을 누적하여 bitwise XOR 한 값
    for(int i = 1; i < s.size(); i++)
        answer = answer ^ s[i];
    
    return answer;
}

• 사용할 수 있는 곡괭이 중 하나를 임의로 선택
• 한 번 선택한 곡괭이는 광물 5개를 캘 때까지 사용
• 광물은 주어진 순서대로 채광 가능
• 모든 광물을 캐거나, 곡괭이를 전부 소모하면 종료
• 위 조건대로 채광 중 가장 피로도가 적게 소모된 경우의 피로도를 리턴

> 뭔가 이것 저것 복잡하게 생각했었는데 dfs로 모든 경우를 다 돌고 이 중 피로도의 최솟값을 리턴하면 되는 문제였다.

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

using namespace std;

// idx = 0: 다이아 = 25, 1: 철 = 5, 2: 돌 = 1
int cntFatigue(int cnt, int pickPower, vector<int> costs) {
    int res = 0;
    
    // 한 곡괭이를 5번 사용할 때 늘어나는 피로도
    for(int i = cnt * 5; i < (cnt + 1) * 5 && i < costs.size(); i++) {
        int cost = costs[i] / pickPower;
        
        // 곡괭이가 광물보다 강하면 피로도는 1씩 증가
        if(cost == 0) res++;
        else res += cost;
    }
    
    return res;
}

// cnt = 채광 사이클 횟수, res = 현재 피로도
void dfs(int cnt, int res, int& answer, vector<int> picks, vector<int> costs) {
    if((picks[0] == 0 && picks[1] == 0 && picks[2] == 0) || cnt * 5 >= costs.size()) {
        answer = min(answer, res);
        return;
    }
    
    // 세 종류의 곡괭이 사용
    for(int i = 0; i < 3; i++)
        // 해당 곡괭이가 0개가 아닐 때
        if(picks[i]) {
            // 개수 감소
            picks[i]--;
            // 사이클은 1, 피로도는 현재 피로도에서 cntFatigue(cnt, (int)pow(5,2 - i))만큼 증가
            dfs(cnt + 1, res + cntFatigue(cnt, (int)pow(5, 2 - i), costs), answer, picks, costs);
            // 다음 dfs에서 사용하기 위해 다시 값 증가
            picks[i]++;
        }
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 100000;
    
    vector<int> costs;
    
    // 각 광물에 해당하는 숫자를 costs 배열에 순서대로 삽입
    for(int i = 0; i < minerals.size(); i++) {
        if(minerals[i][0] == 'd') costs.push_back(25);
        else if(minerals[i][0] == 'i') costs.push_back(5);
        else costs.push_back(1);
    }
    
    // dfs 시작
    dfs(0, 0, answer, picks, costs);
    
    return answer;
}

• 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작 > 여기서 스택을 떠올림
• 스택에 시작되는 과제 명과 해당 과제를 해결하는데 소요되는 시간을 저장하여 가장 최근에 삽입된 과제의 시간을 감소시켜가며 0이 되는 경우에 pop_back 해주면 됨
•  

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

using namespace std;

// 비교자
bool cmp(vector<string> a, vector<string> b) {
    return a[1] < b[1];
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    vector<pair<string, int>> taskStack;
    
    // 과제의 시작 시간 기준으로 정렬
    sort(plans.begin(), plans.end(), cmp);
    
    int curTime = 0;
    
    for(int i = 0; i < plans.size(); i++) {
        // 시작 시간을 분단위 int형 데이터로 만듦
        int nextTime = 60 * stoi(plans[i][1].substr(0, 2)) + stoi(plans[i][1].substr(3, 5));
        
        // 현재 시간이 과제 시작 시간보다 작을 때
        while(curTime < nextTime) {
            // 과제 스택의 사이즈가 0보다 크면
            if(taskStack.size() > 0) {
                
                // 가장 최근의 과제를 진행
                taskStack.back().second--;
                
                // 가장 최근의 과제가 끝나면 
                if(taskStack.back().second == 0) 
                {
                    // 끝낸 과제에 삽입하고
                    answer.push_back(taskStack.back().first);
                    
                    // 과제 스택에서 제거
                    taskStack.pop_back();
                }
            }
            
            // 현재 시간을 1씩 증가
            curTime++;
        }
        
        // 현재 시간이 과제 시작 시간이 되었으므로 
        taskStack.push_back({plans[i][0], stoi(plans[i][2])});
    }
    
    // 과제 스택이 비어있지 않으면 안에 있는 과제를 최신 순서대로 answer에 삽입
    while(taskStack.size() > 0) {
        answer.push_back(taskStack.back().first);
        taskStack.pop_back();
    }
    
    return answer;
}

• 모든 응시자가 거리두기 조건을 지키는지 확인해야함
• 조건 1: 응시자 간 맨해튼 거리가 2보다 커야함
• 조건 2: 맨해튼 거리가 2이하더라도 응시자 사이가 파티션으로 막혀 있으면 조건 충족

첫 번째 이미지를 보면 조건을 만족하는 경우는

• 맨해튼 거리가 2보다 클 때
• x 좌표가 동일하고 맨해튼 거리가 2지만 중간에 파티션이 존재할 때
• y 좌표가 동일하고 맨해튼 거리가 2지만 중간에 파티션이 존재할 때
• 2x2 영역에서 맨해튼 거리가 2이고 응시자가 앉지 않은 나머지 두 곳 모두 파티션이 존재할 때

이렇게 총 4가지이고, 각 places[i]의 응시자들이 모두 이를 만족하는지 체크하면 된다.

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

using namespace std;

int calcDistance(int x1, int y1, int x2, int y2, vector<string> place) {
    int minX = min(x1, x2);
    int minY = min(y1, y2);
    
    // 맨해튼 거리가 2보다 크면
    if((abs(x1 - x2) + abs(y1 - y2)) > 2) return 1;
    
    // x좌표가 동일하고 맨해튼 거리는 2보다 작으나 중간에 파티션이 존재하면
    if(x1 == x2)
        if(place[x1][minY + 1] == 'X') return 1;
    
    // y좌표가 동일하고 맨해튼 거리는 2보다 작으나 중간에 파티션이 존재하면
    if(y1 == y2)
        if(place[minX + 1][y1] == 'X') return 1;
    
    // x ,y 좌표가 동일하지 않을 때
    if(x1 != x2 && y1 != y2) {
        int partition = 0;
        
        // minX, minY 기준으로 2x2 크기의 정사각형 내에 자리 사이에 파티션이 존재할 때
        for(int i = minX; i <= minX + 1; i++) 
            for(int j = minY; j <= minY + 1; j++)
                if(place[i][j] == 'X') partition++;
        
        // 파티션의 개수가 총 2개면
        if(partition == 2) return 1;
    }
    
    // 모든 조건에 충족되지 않을 때
    return 0;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for(int cnt = 0; cnt < 5; cnt++) {
        vector<pair<int, int>> person;
        int result = 1;
        
        // 응시자가 있는 좌표 저장
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                if(places[cnt][i][j] == 'P') person.push_back({i, j});
        
        // 각 응시자를 기준으로 조건을 충족하는지 체크
        // 충족되지 않는 응시자가 나오면 (result == 0) 반복 중지
        for(int i = 0; i < person.size() && result == 1; i++)
            for(int j = i + 1; j < person.size() && result == 1; j++)
                    result = calcDistance(person[i].first, person[i].second,
                            person[j].first, person[j].second, places[cnt]);
        
        // 결과 삽입
        answer.push_back(result);
    }
    
    return answer;
}

• 직선 n개 중에서 2개씩 뽑아서 해당 두 직선의 교점을 구해야함
• 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않음 
• 모든 직선 쌍은 교점이 유일하게 존재하거나 평행함
• 문제 아래의 참고 사항에서 두 직선이 평행한지와 두 직선의 교점을 구하는 방법이 나와있으므로 참고하면 됨
• 모든 직선쌍의 교점을 구한 뒤 해당 영역을 그리기 위해 가장 작은 x, y 좌표와 가장 큰 x, y 좌표를 구해야함
• 이후 maxX - minX, maxY - minY가 그릴 영역의 가로, 세로가 됨
• 영역을 그린 뒤 그래프의 좌표와 그린 영역의 좌표가 다른 것을 감안해 좌표이동을 하여 '*'을 해당 좌표에 삽입

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

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    vector<pair<int, int>> coor;
    // minX, maxX, minY, maxY 초기화
    int minX = INT32_MAX, maxX = INT32_MIN, minY = INT32_MAX, maxY = INT32_MIN;
    
    for(int i = 0; i < line.size(); i++) {
        for(int j = i + 1; j < line.size(); j++) {
            
            // 이 값이 0이면 두 직선은 평행
            int isParallel = line[i][0] * line[j][1] - line[i][1] * line[j][0];
            
            // 0이 아니면 교점이 존재
            if(isParallel) {
                long long x = (1LL * line[i][1] * line[j][2] - 1LL * line[i][2] * line[j][1]);
                long long y = (1LL * line[i][2] * line[j][0] - 1LL * line[i][0] * line[j][2]);
                
                // 이 중 정수로만 표현되는 좌표를 저장    
                if(x % isParallel == 0 && y % isParallel == 0) coor.push_back({x / isParallel, y / isParallel});
            }
        }
    }
    
    // 정렬 후 중복되는 좌표 제거
    sort(coor.begin(), coor.end());
    coor.erase(unique(coor.begin(), coor.end()), coor.end());
    
    // minX, maxX, minY, maxY를 구함
    for(int i = 0; i < coor.size(); i++) {
        minX = min(minX, coor[i].first);
        maxX = max(maxX, coor[i].first);
        minY = min(minY, coor[i].second);
        maxY = max(maxY, coor[i].second);
    }
    
    // 각각 영역의 가로, 세로
    int x = maxX - minX, y = maxY - minY;
    
    // 해당 영역의 크기만큼 answer를 '.'로 초기화
    for(int i = 0; i <= y; i++) {
        string board(x + 1, '.');
        answer.push_back(board);
    }
    
    // 좌표이동 후 '*'를 삽입
    for(int i = 0; i < coor.size(); i++) 
        answer[maxY - coor[i].second][coor[i].first - minX] = '*';
    
    return answer;
}

• 단순한 bfs 문제
• 연결된 같은 색상으로 이루어진 영역의 개수와, 가장 넓은 영역의 넓이를 구하는 문제

> 정답률이 낮아서 좀 난이도가 있는 문제인가 싶었는데 열어보니 그냥 bfs로 해결하면 되는 문제였다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

//bfs
int bfs(int i, int j, int m, int n, vector<vector<int>> picture) {
    int color = picture[i][j];
    int size = 1;
    queue<pair<int, int>> q;
    q.push({i, j});
    visited[i][j] = true;
    
    while(!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
        
        // 4방향으로 이동
        for(int i = 0; i < 4; i++) {
            int nx = curX + dirX[i];
            int ny = curY + dirY[i];
            
            if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
                // 다음으로 방문한 좌표의 색상이 color와 같고 방문한 적 없으면
                if(picture[nx][ny] == color && !visited[nx][ny]) {
                    // 방문 여부 갱신
                    visited[nx][ny] = true;
                    // 방문 좌표 갱신
                    q.push({nx, ny});
                    // 영역 너비 증가
                    size++;
                }
            }
        }
    }
    
    return size;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;
    
    // 방문 배열 초기화
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            visited[i][j] = false;
    
    // 색이 칠해져 있고 방문한적 없으면 bfs 수행
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(picture[i][j] != 0 && !visited[i][j]) {
                // 가장 넓은 영역 구하기
                max_size_of_one_area = max(max_size_of_one_area, bfs(i, j, m, n, picture));
                // 영역 개수 증가
                number_of_area++;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    
    return answer;
}

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

using namespace std;

int solution(vector<int> cards) {
    int answer = 0;
    int n = cards.size();
    // 해당 숫자의 카드가 선택되었는지 체크
    bool selected[101] = {false};
    vector<int> results;
    
    for(int i =0; i < n; i++) {
        int cur = cards[i], cnt = 0;
        
        // 이미 선택된 카드가 나오지 않을때까지 카드 뽑기
        while(!selected[cur]) {
            selected[cur] = true;
            cur = cards[cur - 1];
            cnt++;
        }
        
        if(cnt > 0) results.push_back(cnt);
    }
    
    if(results.size() > 1) {
    	// 배열을 내림차순으로 정렬
        sort(results.begin(), results.end(), greater<int>());
        // 가장 큰 값 2개를 곱한 뒤 리턴
        return results[0] * results[1];
    }
    return 0;
}​

우선순위 큐를 이용하면 간단하게 풀 수 있는 문제

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

using namespace std;

int solution(int n, int k, vector<int> enemy) {
    int sum = 0;
    
    // 우선순위 큐를 오름차순으로 정렬
    priority_queue<int, vector<int>, greater<int>> prio_q;
    
    for(int i = 0; i < enemy.size(); i++) {
        prio_q.push(enemy[i]);
        
        // 무적권보다 라운드 수가 많아지면
        if(prio_q.size() > k) { 
        	// 적이 가장 작은 라운드의 적 수를 더함
            sum += prio_q.top();
            // 이후 제거
            prio_q.pop();
        }
        
        // 적의 수가 병사보다 많으면 막아낸 라운드 수 리턴
        if(sum > n) return i;
    }
    
    return enemy.size();
}