99코딩

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

정사각형에 2차원 배열인거 보고 분할정복 생각했지만 천천히 다시 읽어보니 관련 없는 문제였다

위에서 우하단을 기준으로 좌상단, 우상단, 좌하단이 1이상이면 정사각형

여기서 우하단에 네 값 중 가장 작은 값 + 1을 하면 해당 정사각형의 한 변의 길이가 됨

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

using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    
    int row = board.size();
    int col = board[0].size();
    
    // (1, 1)부터 시작 > 우하단을 기준으로 하기 때문
    for(int i = 1; i < row; i++) {
        for(int j = 1; j < col; j++) {
        	//0이면 정사각형이 불가능하고 1보다 크면 이미 확인한 구간이지만 중복된 구간을 체크하지 않기 때문에 1보다 클 일이 없음
            if(board[i][j] == 1) {
                board[i][j] = min({board[i-1][j-1], board[i-1][j], board[i][j-1]}) + 1;
                answer = max(answer, board[i][j]);
            }
        }
    }

    return answer * answer;
}

• 서로 같은 거리에서 토크 값이 같으려면 몸무게의 비율 = 1:1
• 2m, 4m 거리에서 토크 값이 같으려면 몸무게의 비율 = 1:2
• 2m, 3m 거리에서 토크 값이 같으려면 몸무게의 비율 = 3:2 = 1:3/2
• 3m, 4m 거리에서 토크 값이 같으려면 몸무게의 비율 = 4:3 = 1:4/3

> 특정 인원의 몸무게를 weight라 할 때 weight값의 1:1, 1:2, 1:3/2, 1:4/3에 해당하는 값이 존재하는지 확인해야함

> weightA와 weightB가 다른 경우에는 단순히 weightB에 해당하는 인원 수를 answer에 더하면 되지만 같은 경우에는 중복을 제거하기 위해 n명 중에서 2명을 뽑는 경우의 수 식을 이용해야함

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> weights) {
    long long answer = 0;
    // 각 몸무게에 해당하는 인원 수 저장용 배열
    vector<long long> count(1001, 0);
    long long weight = 0;
    
    // index을 몸무게로 가지는 인원의 수를 저장
    for(int i = 0; i < weights.size(); i++) {
        count[weights[i]]++;
    }
    
    // 특정 몸무게가 2명 이상일 경우 n(n-1)/2 식을 통해 짝의 수를 구함
    for(int i = 100; i < 1001; i++) {
        if(count[i] >= 2) {
            answer += (count[i] * (count[i] - 1)) / 2;
        }
    }
    
    //weight의 1:2, 1:3/2, 1:4/3에 해당하는 몸무게를 가지는 인원 수를 구해서 짝을 만듦
    for(int i = 0; i < weights.size(); i++) {
        // 1:2
        weight = weights[i] * 2;
        if(weight <= 1000) answer += count[weight];
        
        // 2:3
        if(weights[i] % 2 == 0) {
            weight = weights[i] * 3 / 2;
            if(weight <= 1000) answer += count[weight];
        }
        
        // 3:4
        if(weights[i] % 3 == 0) {
            weight = weights[i] * 4 / 3;
            if(weight <= 1000) answer += count[weight];
        }
    }
    
    return answer;
}

• arrayA의 카드들에 적힌 모든 숫자를 나눌 수 있고, arrayB의 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a 
• arrayB의 카드들에 적힌 모든 숫자를 나눌 수 있고, arrayA의 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

• 위 둘 중 하나를 만족하는 가장 큰 양의 정수 a를 구해야 함
• 특정 카드들에 적힌 모든 숫자를 나눌 수 있음 => 최대공약수
• 한 쪽의 최대 공약수를 구해서 다른 한 쪽을 나눌 수 없는지 체크 후 양측에 각각 해당하는 값이 있다면 더 큰 값을 리턴

> arrayA의 최대공약수를 구하고 해당 값이 arrayB를 나눌 수 있는지 체크 후 나눌 수 없다면 answer 값과 비교해서 크다면 저장

> arrayB의 최대공약수를 구하고 해당 값이 arrayA를 나눌 수 있는지 체크 후 나눌 수 없다면 answer 값과 비교해서 크다면 저장

#include <string>
#include <vector>

using namespace std;

// 최대 공약수
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

// 값 비교
int compare(int a, int b) {
    if(a > b) return a;
    return b;
}

int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    int length = arrayA.size();
    
    // arrayA의 최대공약수 구하기
    int gcdValue = arrayA[0];
    
    for(int i = 1 ; i < length; i++) {
        gcdValue = gcd(gcdValue, arrayA[i]);
        if(gcdValue == 1) break;
    }
    
    // 최대공약수가 1이면 패스
    if(gcdValue != 1) {
        int cnt = 0;
        
        // arrayB에 나눌 수 있는 값이 있는지 체크
        for(int i = 0; i < length; i++) {
            if(arrayB[i] % gcdValue == 0) break;    
            cnt++;
        }
        
        //cnt == length면 answer = 최대공약수
        if(cnt == length) answer = gcdValue;
    }
    
    // arrayB의 최대공약수 구하기
    gcdValue = arrayB[0];
    
    for(int i = 0; i < length; i++) {
        gcdValue = gcd(gcdValue, arrayB[i]);
        if(gcdValue == 1) break;
    }
    
    // 최대공약수가 1이면 패스
    if(gcdValue != 1) {
        int cnt = 0;
        
        // arrayA에 나눌 수 있는 값이 있는지 체크
        for(int i = 0; i < length; i++) {
            if(arrayA[i] % gcdValue == 0) break;
            cnt++;
        }
        
        //cnt == length면 answer와 비교해서 더 큰 놈을 answer에 저장
        if(cnt == length) answer = compare(answer, gcdValue);
    }
    
    return answer;
}

• 앞에서부터 n개 단위로 문자열을 잘라 압축시킨 뒤의 문자열 길이가 가장 짧은 n의 값을 구하는 문제

> 1부터 문자열의 길이까지를 단위로 하여 압축한 뒤 개중 가장 짧은 길이를 리턴

> 입력받은 단위만큼 비교하여 압축이 가능한지 가능하다면 총 몇 번 압축 가능한지 판별

> 이후 압축이 가능하다면 압축된 형태로 str을 갱신 후 나머지 구간을 반복

#include <string>
#include <vector>

using namespace std;

// cnt = 압축 단위, str = 문자열
int stringCompressor(int cnt, string str) {
    for(int i = 0; i < str.size();) {
    	// i부터 cnt만큼 문자열을 자름
        string cmpStr = str.substr(i, cnt);
        
        // cmpStr과 같은 문자열의 개수(자신 포함)
        int cntSameStr = 1;
        
        for(int j = i + cnt;j < str.size(); j += cnt) {
        	// j부터 cnt만큼 자른 문자열이 cmpStr과 같으면 cntSameStr++, 다르면 break
            if(cmpStr == str.substr(j, cnt)) cntSameStr++;
            else break;
        }
        
        // cntSameStr == 1이면 같은 문자열 없음으로 다음 구간으로 넘김
        if(cntSameStr == 1) {
            i += cnt;
            continue;
        }
        
        // cntSameStr의 개수 + cmpStr의 형태로 만듦
        cmpStr = to_string(cntSameStr) + cmpStr;
        // 압축되지 않는 나머지 문자열을 자름
        string remainStr = str.substr(i + cnt * cntSameStr);
        // str의 형태를 갱신
        str = str.substr(0, i) + cmpStr + remainStr;
        
        i += cmpStr.size();
    }
    
    return str.size();
}

int solution(string s) {
    int answer = s.size();
    
    //1부터 해당 문자열의 사이즈만큼 압축을 반복
    for(int i = 1; i <= s.size(); i++) {
        answer = min(answer, stringCompressor(i ,s));
    }
    
    return answer;
}

 풀고 나니까 1부터 문자열의 사이즈만큼이 아니라 1부터 문자열 사이즈의 1/2까지만 반복하는 것이 더 효율적이었을 것 같다. 

> 어차피 압축 단위가 문자열의 절반보다 크면 압축 안됨

• 겹치는 구간에 있는 미사일은 하나의 미사일로 전부 요격 가능. 개구간(s, e)의 미사일은 s와 e에서 발사된 요격 미사일로 요격 불가

> 일단 주어지는 targets 배열을 오름차순으로 정렬

> 이후 현재 타겟의 e보다 s가 작은 타겟들을 전부 패스

> 현재 타겟의 e보다 e가 작은 타겟이 나올 시 요격 미사일 수 값을 증가 시키고 e 값을 다음 타겟의 e 값으로 갱신

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    
    // 배열을 오름차순으로 정렬
    sort(targets.begin(), targets.end());
    
    for(int i = 0; i < targets.size();) {
    	// 현재 타겟의 e 값을 저장
        int end = targets[i++][1];
        answer++;
        
        // 다음 타겟의 s가 현재 타겟의 e보다 작다면 반복
        for(; i < targets.size() && targets[i][0] < end;) {
        	//다음 타겟의 e가 현재 타겟의 e보다 작다면 e를 갱신
            if(targets[i][1] < end) end = targets[i][1];
            i++;
        }
    }
    
    return answer;
}