99코딩

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

#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();
}

• 출발점에서 레버까지 bfs 수행
• 레버에서 출구까지 bfs 수행

> 총 2번 bfs를 수행하면 되는 문제

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

using namespace std;

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

int bfs(vector<string> maps, queue<pair<int, int>> q, int n, int m, char target) {
    // 방문 배열
    int dist[n][m];
    // -1로 초기화
    memset(dist, -1, sizeof(dist));
    
    // 시작 지점의 방문 배열 값은 0
    dist[q.front().first][q.front().second] = 0;
    
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int nx = cur.first + dirX[i];
            int ny = cur.second + dirY[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            if(maps[nx][ny] == 'X' || dist[nx][ny] != -1) continue;
            
            // target을 만나면 해당 target까지 이동한 횟수 리턴
            if(maps[nx][ny] == target) return dist[cur.first][cur.second] + 1;
            
            // 아니라면 방문 횟수를 저장하고 현재 위치 갱신
            dist[nx][ny] = dist[cur.first][cur.second] + 1;
            
            q.push({nx, ny});
        }
    }
    
    return -1;
}

int solution(vector<string> maps) {
    int answer = 0;
    int n = maps.size();
    int m = maps[0].size();
    
    // 각각 레버, 출구로 갈 때 쓸 큐
    queue<pair<int, int>> toLever, toExit;
    
    // 각각 출발점의 좌표와 레버의 좌표 저장
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(maps[i][j] == 'S') toLever.push({i, j});
            else if(maps[i][j] == 'L') toExit.push({i, j});
        }
    }
    
    int tmp;
    
    // 레버로
    answer = bfs(maps, toLever, n, m, 'L');
    
    // 출구로
    if(answer == -1) return -1;
    else tmp = bfs(maps, toExit, n, m, 'E');
    
    if(tmp == -1) return -1;
    else answer += tmp;
    
    return answer;
}

> 위를 그대로 구현하면 됨

#include <string>
#include <vector>
#include <stack>

using namespace std;

// 올바른 문자열인지 체크
bool isCorrect(string s) {
    stack<char> str;
    for(int i = 0; i < s.size(); i++) {
        if(!str.empty() && s[i] == ')' && str.top() == '(') str.pop();
        else str.push(s[i]);
    }
    
    if(str.empty()) return true;
    return false;
}

// 괄호 변환
string convert(string s) {
	// 빈 문자열이면 빈 문자열 반환
    if (s == "") return "";
    
    // 균형잡힌 문자열을 구하기 위해 인덱스를 구함
    int idx = 0, cnt = 0;
    for(;idx < s.size(); idx++) {
        if(s[idx] == '(') cnt++;
        else cnt--;
        
        if(cnt == 0) break;
    }
    
    // 균형잡힌 문자열
    string str1 = s.substr(0, idx + 1);
    // 나머지 문자열
    string str2 = s.substr(idx + 1);
    
    // str1이 올바른 문자열일 때
    if(isCorrect(str1)) return (str1 + convert(str2));
    // str2가 올바른 문자열이 아닐 때
    else {
    	// 앞 뒤 제거
        str1.erase(str1.begin());
        str1.erase(str1.end()-1);
        
        // 괄호 뒤집기
        for(int i = 0; i < str1.size(); i++) {
            if(str1[i] == '(') str1[i] = ')';
            else str1[i] = '(';
        }
        
        // 4-1~3과 위에서 만든 올바른 문자열을 리턴
        return ("(" + convert(str2) + ")" + str1);
    }
}

string solution(string p) {
    return convert(p);
}

• board 주고 최소 움직임 구해라 = bfs
• 한 칸씩 이동하는 것이 아닌 한 방향으로 장애물이나 보드의 끝에 부딫힐 때까지 이동
• "R"은 시작 위치, "D"는 장애물 위치, "G"는 목표 위치

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

using namespace std;

queue<pair<int, int>> q;
int dirX[4] = {1, -1, 0, 0};
int dirY[4] = {0, 0, 1, -1};
// 방문 여부 및 방문 시까지 몇 번 이동했는지 체크용
int dist[101][101];

int solution(vector<string> board) {
    int answer = 0;
    
    int height = board.size();
    int width = board[0].size();
    
    // 시작 위치 찾기
    for(int i = 0;i < height; i++) {
        for(int j = 0; j < width; j++) {
            if(board[i][j] == 'R') {
                q.push({i, j});
                dist[i][j] = 1;
            }
        }
    }
    
    // BFS
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        
        // 4방향으로
        for(int i = 0; i < 4; i++) {
            int nx = cur.second;
            int ny = cur.first;
            
            // 현재 좌표의 값이 G면 도착, 출발점부터 1이 있기 때문에 리턴 시 -1을 해줌
            if(board[cur.first][cur.second] == 'G')
            return dist[cur.first][cur.second] - 1;
            
            while(1) {
                nx += dirX[i];
                ny += dirY[i];
                
                // 보드의 끝 또는 장애물과 만나면 이동 종료
                if(nx < 0 || ny < 0 || nx >= width || ny >= height) {
                    nx -= dirX[i];
                    ny -= dirY[i];
                    break;
                }
                
                if(0 <= nx && nx < width && 0 <= ny && ny < height && board[ny][nx] == 'D'){
                    nx -= dirX[i];
                    ny -= dirY[i];
                    break;
                }
            }
            
            // 방문한 적 없으면 해당 좌표 방문까지 걸린 횟수 저장 및 출발점 갱신
            if(dist[ny][nx] == 0) {
                dist[ny][nx] = dist[cur.first][cur.second] + 1;
                q.push({ny, nx});
            }
        }
    }
    
    // 도착 못하면 -1 리턴
    return -1;
}

• 행렬에서 주어진 영역의 테두리를 시계 방향으로 회전
• 이를 수행 후 위치가 바뀐 숫자들 중 가장 작은 숫자를 배열에 담음
• 위를 반복

> 처음에 보고 복잡하게 생각했는데 위에 생각만큼 어려운 문제는 아니었다.

> 예시 기준으로 위, 오른쪽, 아래, 왼쪽 순서로 배열에 값과 좌표를 담으며 가장 작은 숫자를 찾음

> 값이 들어있는 배열의 원소들을 rotate 함수를 통해 오른쪽으로 하나씩 이동

> 다시 좌표에 순서대로 값들을 저장

> 위를 반복

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

using namespace std;

int table[101][101];

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    
    int num = 1;
    
    // 행렬 생성
    for(int i = 1; i <= rows; i++)
        for(int j = 1; j <= columns; j++)
            table[i][j] = num++;

    for(int i = 0; i < queries.size(); i++) {
        // 값 저장용
        vector<int> tmp;
        // 좌표 저장용
        vector<pair<int, int>> coordinate;
        int minVal = 10001;
        
        // 사용하기 쉽게 좌표 변수 생성
        int startY = queries[i][0];
        int startX = queries[i][1];
        int endY = queries[i][2];
        int endX = queries[i][3];
        
        // 위쪽
        for(int i = startX; i <= endX; i++) {
            tmp.push_back(table[startY][i]);
            //최솟값 찾기
            minVal = min(minVal, table[startY][i]);
            coordinate.push_back({startY, i});
        }
        
        // 오른쪽
        for(int i = startY + 1; i <= endY ; i++) {
            tmp.push_back(table[i][endX]);
            //최솟값 찾기
            minVal = min(minVal, table[i][endX]);
            coordinate.push_back({i, endX});
        }
        
        // 아래쪽
        for(int i = endX - 1; i >= startX; i--) {
            tmp.push_back(table[endY][i]);
            //최솟값 찾기
            minVal = min(minVal, table[endY][i]);
            coordinate.push_back({endY, i});
        }
        
        // 왼쪽
        for(int i = endY - 1; i >= startY + 1; i--) {
            tmp.push_back(table[i][startX]);
            //최솟값 찾기
            minVal = min(minVal, table[i][startX]);
            coordinate.push_back({i, startX});
        }
        
        // 값들을 오른쪽으로 한 칸씩 옮기기
        rotate(tmp.rbegin(), tmp.rbegin() + 1, tmp.rend());
        
        // 좌표에 값을 순서대로 저장
        for(int i = 0; i < coordinate.size(); i++)
            table[coordinate[i].first][coordinate[i].second] = tmp[i];
        
        // 최솟값 저장
        answer.push_back(minVal);
    }
    
    return answer;
}

• 주어지는 k 값으로 콜라츠 추측 수행
• 이후 만들어지는 그래프에서 주어진 범위만큼 넓이를 구하면 됨

> 설명이 많긴한데 그냥 주어진 조건 수행 후 만들어지는 그래프에서 주어지는 각 범위마다 넓이를 구하면 됨

#include <string>
#include <vector>

using namespace std;

vector<double> solution(int k, vector<vector<int>> ranges) {
    vector<double> answer;
    vector<int> hail;
    
    hail.push_back(k);
    
    // 결과가 1보다 크면 작업 반복
    while(k != 1) {
    	// 입력된 수가 짝수라면 2로 나눔
        if(k % 2 == 0) k /= 2;
        // 입력된 수가 홀수라면 3을 곱하고 1을 더함
        else k = (k * 3) + 1;
        
        // 각 작업마다 나오는 값 저장
        hail.push_back(k);
    }
    
    for(int i = 0; i < ranges.size(); i++) {
    	// 주어진 범위의 시작점
        int start = ranges[i][0];
        // 주어진 범위의 끝점
        int end = hail.size() - 1 + ranges[i][1];
        double tmp = 0;
        
        // 주어진 범위의 너비 계산
        for(int j = start; j < end; j++)
            tmp += (double)(hail[j] + hail[j + 1]) / 2;
        
        // 시작점이 끝점보다 크다면 결과는 -1
        if(start > end) answer.push_back(-1.0);
        else answer.push_back(tmp);
    }
    
    return answer;
}

• 연산자의 우선순위를 임의로 정하여 입력받은 식의 값의 절댓값 중 가장 큰 값을 구해야함
• 연산자의 우선순위는 중복 불가
• 주어지는 연산자는 +, -, *

> 연산자 간의 순열을 이용, 주어지는 연산자가 3개뿐이므로 순열은 총 3!가지

> + > - > * 순서가 될 시 +를 먼저 계산 후 -, * 순서로 계산하도록 반복하면 됨

> 연산 후 피연산자 2개를 삭제 후 결과를 해당 위치에 삽입하고, 연산자의 삭제도 필요

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

using namespace std;

long long calc(char op, long long a, long long b) {
    if(op == '+')
        return a + b;
    else if(op == '-')
        return a - b;
    else if(op == '*')
        return a * b;
}

long long solution(string expression) {
    long long answer = 0;
    
    // 피연산자 벡터
    vector<long long> operands;
    // 연산자 벡터
    vector<char> operators;
    string tmp;
    
    // 연산자와 피연산자를 분리
    for(int i = 0; i < expression.size(); i++) {
        if(expression[i] >= '0' && expression[i] <= '9')
            tmp += expression[i];
        else {
            operators.push_back(expression[i]);
            operands.push_back(stoll(tmp));
            tmp = "";
        }
    }
    
    operands.push_back(stoll(tmp));
    
    // 주어진 연산자
    string oper = "*+-";
    
    do {
    	//연산자와 피연산자 배열 복사
        vector<long long> operandTmp = operands;
        vector<char> operatorTmp = operators;
        
        // 연산자 수만큼 반복
        for(int i = 0; i < 3; i++) {
        	// 연산자 배열 크기만큼 반복
            for(int j = 0; j < operatorTmp.size();) {
                if(operatorTmp[j] == oper[i]) {
                    long long tmp = calc(operatorTmp[j], operandTmp[j], operandTmp[j + 1]);
                    
                    // 피연산자 2개를 지움
                    operandTmp.erase(operandTmp.begin() + j);
                    operandTmp.erase(operandTmp.begin() + j);
                    // 해당 위치에 결과값 삽입
                    operandTmp.insert(operandTmp.begin() + j, tmp);
                    
                    // 사용한 연산자를 지움
                    operatorTmp.erase(operatorTmp.begin() + j);
                }
                else
                    j++;
            }
        }
        
        // 절댓값이 가장 큰 경우 찾기
        answer = max(answer, abs(operandTmp[0]));
    } while (next_permutation(oper.begin(), oper.end())); // 순열
    
    return answer;
}

> 계속 5번이 틀려서 질문 목록을 보니 문자열 순서가 *+-되어야한다는 글이 있어서 바꿔보니 해결되었다.

> 왜 그런지에 대한 답변은 어디에도 없었다....

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

using namespace std;

int elevator(int storey) {
	// 현재 층 수가 10층 이하일 때 내려가는게 빠른지 올라가서 10층을 내려가는게 빠른지 판별
    if(storey < 10) return min(storey, 11 - storey);
    int cntDown = storey % 10;
    int cntUp = 10 - storey % 10;
    
    // 현재 층에서 내려가는 횟수와 현재 층에서 올라가는 횟수 중 작은 값을 선택하여 최소 횟수를 계산
    return min(elevator((storey - cntDown) / 10) + cntDown, elevator((storey + cntUp) / 10) + cntUp);
}

int solution(int storey) {
    return elevator(storey);
}