코딩생존기

현재 남은 병사에서 만약 막을 수 있다면 막으면서 해당 값을 최대값으로 저장한다. 

그후 만약 저장된 값을 검사해서 

1.만약 기존 값이 크다면 전의 걸 무적권을 쓰고 해당 수만큼 병사를 돌려받는다.

2.만약 기존 값이 현재의 수보다 작을 때 막을 수 있으면 막고

3.아닐 때 저장된 큰 값이 없는 경우는 무적권을 쓰거나 게임오버

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

using namespace std;
//큰값 저장 및 검사
int solution(int n, int k, vector<int> enemy) {
    priority_queue<int> pq;
    int answer = 0;
    for(int i=0;i<enemy.size();i++){
        if(n>=enemy[i]){        //만약 현재가진 병사로 막을 수 있다면
            n-=enemy[i];
            pq.push(enemy[i]);      //최대적 수 저장
        }else{
            if(k>0){            //무적권이 남아있다면
               if(!pq.empty()&&pq.top()>enemy[i]){  //만약 전에 최대였던 수가 현재적보다 크다면
                   n+=pq.top();                              //무적권을 사용해서 돌려받기
                   pq.pop();
                   pq.push(enemy[i]);
                   n-=enemy[i];                 //전에 무적권을 쓰고 지금꺼는 병사로 막기
                }
                k--;
            }else
                return i;
        }
    }
    
    return enemy.size();
}

하노이의 탑은 유명한 재귀 문제이다.

매번 볼때마다 어렵긴하지만 그냥 외우는게 답일 것 같다.

한개만 남아있을 때는 옮겨야하는기둥에 바로 옮기면 되고 

n-1가 남아있을 때는 sub기둥에 n-1를 옮겨두면 된다.

그리고 sub기둥에 있는 것도 end로 하나씩 옮기면 된다.

핵심 코드 

  if(n==1){       //한개만 남았다면 from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
    }else{
        //n-1개를 from -> sub로 옮기기
        hanoi(n-1,start,sub,end,answer);
        
        //from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
        //sub-> to
        hanoi(n-1,sub,end,start,answer);
    }

전체코드

#include <string>
#include <vector>

using namespace std;
void hanoi(int n,int start,int end,int sub,vector<vector<int>> &answer){
    
    vector<int> v;
    if(n==1){       //한개만 남았다면 from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
    }else{
        //n-1개를 from -> sub로 옮기기
        hanoi(n-1,start,sub,end,answer);
        
        //from-> to
        v.push_back(start);
        v.push_back(end);
        answer.push_back(v);
        //sub-> to
        hanoi(n-1,sub,end,start,answer);
    }
    
    return;
}


vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;
    hanoi(n,1,3,2,answer);
    
    return answer;
}

BFS문제이다.

BFS이지만 방향에 따라 장애물이나 끝에 도달할 때 까지 진행한다는 차이점이 있다. 

만약 G에 도달하면 time 최소시간 time을 반환해준다.

#include <string>
#include <vector>
#include <queue>
#define MAX 101
int w,h;
int dirX[4]={-1,1,0,0};
int dirY[4]={0,0,-1,1};
using namespace std;
int BFS(int i,int j,vector<string> board){
    queue<pair<pair<int,int>,int>> q;
    bool visited[MAX][MAX]={0,};
    int time=1e9;
    
    q.push({{i,j},0});
    visited[i][j]=true;
    
    while(!q.empty()){
        int curx = q.front().first.first;
        int cury = q.front().first.second;
        int cur_time = q.front().second;
        q.pop();
        if(board[curx][cury]=='G') time=min(time,cur_time);
        
       for (int i = 0; i < 4; i++) {
            int nx = curx + dirX[i];
            int ny = cury + dirY[i];

            if ((nx < 0 || nx >= w || ny < 0 || ny >= h)|| board[nx][ny]=='D') continue;           //못가는 곳은 넘어가기  
                
            while(true){            //장애물 있는데까지 전진
                nx+=dirX[i];
                ny+=dirY[i];
                
                if ((nx < 0 || nx >= w || ny < 0 || ny >= h)|| board[nx][ny]=='D'){
                    nx-=dirX[i];
                    ny-=dirY[i];                //장애물까지 갔으니 그전 좌표 계산
                    break;
                }
            }
            if(visited[nx][ny]) continue;
           
            q.push({ {nx,ny},cur_time + 1 });
            visited[nx][ny] = true;
        }
    }
    
    return time==1e9? -1: time;
}

int solution(vector<string> board) {
    int answer = 0;
    w=board.size();
    h=board[0].size();
    for(int i=0;i<w;i++){
        for(int j=0;j<h;j++){
            if(board[i][j]=='R'){
                answer=BFS(i,j,board);
            }
        }
    }
    return answer;
}

사람을 발견했을 때

BFS를 통해 탐색을 해서 만약 맨해튼 거리가 2이하인 사람이 있다면 false를 반환해주면 된다. 

이때 만약 탐색 중에 X  즉 파티션을 만나게 되면 파티션 너머는 탐색할 필요가 없어서 continue 처리를 해주면 된다.

그리고 만약 false가 하나라도 있다면 그 대기실은 거리두기를 지키지않는 것이여서 break;처리를 해주면 된다.

#include <string>
#include <vector>
#include <queue>
using namespace std;

int dx[4] = {-1, 1, 0, 0};  // 왼, 오, 아래, 위
int dy[4] = {0, 0, 1, -1};

bool check_dist(int i, int j, vector<string> place) {           //BFS
    bool visited[5][5] = {false};
    queue<pair<pair<int, int>, int>> q;
    visited[i][j] = true;
    q.push({{i, j}, 0});
    
    while (!q.empty()) {
        int cur_x = q.front().first.first;
        int cur_y = q.front().first.second;
        int dist = q.front().second;
        q.pop();
        
        for (int h = 0; h < 4; h++) {
            int nx = cur_x + dx[h];
            int ny = cur_y + dy[h];
            
            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            
            if (visited[nx][ny] || place[nx][ny] == 'X') continue;        //파티션이 있는 경우 너머는 탐색할 필요 없음  
            
            if (place[nx][ny] == 'P' && dist + 1 <= 2) {            //사람이 있는데 맨해튼거리가 지켜지지 않으면
                return false;
            }
            
            visited[nx][ny] = true;
            q.push({{nx, ny}, dist + 1});
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    
    for (auto place : places) {
        bool check = true;
        
        for (int i = 0; i < 5 && check; i++) {
            for (int j = 0; j < 5; j++) {
                if (place[i][j] == 'P') {
                    if (!check_dist(i, j, place)) {
                        check = false;
                        break;
                    }
                }
            }
        }
        
        answer.push_back(check ? 1 : 0);
    }
  
    return answer;
}

처음에는 문제를 이해를 못했다. 하지만 천천히 문제를 읽어보니 

문제에서 주어진 열을 기준으로 정렬을 하는데 이 때 열의 값이 같다면

기본키 즉 첫번째 열을 기준으로 내림차순 정렬하고 

정렬후에 row_begin 번째 행부터 row_end 번째 행까지의 합을 xor해주면 된다는 것이다.

이때 xor은 합을 answer에 xor 연산을 계속 해주면 된다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int cmpnum;
bool cmp(vector<int> a, vector<int> b) {
    if (a[cmpnum] == b[cmpnum]) {      //만약 col번째 열의 값이 같다면
        // 기본키 (첫 번째 열) 기준 내림차순 정렬
        return a[0] > b[0];
    }

    return a[cmpnum] < b[cmpnum]; //아니라면 
}


int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    cmpnum = col - 1;           //col번째 열
    sort(data.begin(), data.end(), cmp);          //오름차순 정렬

    for (int i = row_begin - 1; i < row_end; i++) {
        int sum = 0;
        for (int j = 0; j < data[i].size(); j++) {
            sum += data[i][j] % (i + 1);
        }
        answer ^= sum;               //각각의 합을 계속 xor해주기
    }

    return answer;
}

BFS를 활용하여 푸는 문제이다.

기본 문제와 다른점은 레버가 있고 이 레버를 당기고 출구까지 이동해야한다는 것이다. 

일단 출발점, 레버, 도착점을 저장하고 출발~ 레버를 BFS 수행하고 만약 레버까지 갈 수 있는 경로가 있다면 레버~ 도착점까지 BFS를 수행한다.

#include <string>
#include <vector>
#include <queue>
#define MAX 100
using namespace std;

int w, h;
int dirX[4] = { -1, 1, 0, 0 };        //왼,오,위,아래
int dirY[4] = { 0, 0, -1, 1 };

int bfs(int stx, int sty, int dtx, int dty, vector<string> maps) {
    queue<pair<pair<int, int>, int>> q;                 //좌표 및 시간 저장      {{x,y},time}
    bool visited[MAX][MAX] = { 0, };
    int time = 1e9;

    q.push({ {stx,sty},0 });
    visited[stx][sty] = true;

    while (!q.empty()) {
        int curx = q.front().first.first;
        int cury = q.front().first.second;
        int cur_time = q.front().second;
        q.pop();

        if (curx == dtx && cury == dty) time = min(time, cur_time);

        for (int i = 0; i < 4; i++) {
            int nx = curx + dirX[i];
            int ny = cury + dirY[i];

            if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;           //못가는 곳은 넘어가기  
            if (visited[nx][ny] || maps[nx][ny] == 'X')continue;

            q.push({ {nx,ny},cur_time + 1 });
            visited[nx][ny] = true;
        }
    }

    return time == 1e9 ? 0 : time;
}
int solution(vector<string> maps) {
    pair<int, int> start;
    pair<int, int> laber;
    pair<int, int> dest;

    w = maps.size();
    h = maps[0].size();

    int findcnt = 0;

    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            if (findcnt == 3) break;

            if (maps[i][j] == 'S') {
                start = { i,j };
                findcnt++;
            }
            else if (maps[i][j] == 'L') {
                laber = { i,j };
                findcnt++;
            }
            else if (maps[i][j] == 'E') {
                dest = { i,j };
                findcnt++;
            }
        }
    }

    int sttolb = bfs(start.first, start.second, laber.first, laber.second, maps);           //출발점 ~ 라벨있는 곳까지 
    int lbtodt = sttolb ? bfs(laber.first, laber.second, dest.first, dest.second, maps) : -1;           //출발점~ 라벨있는 곳까지 갈 수 있다면 라벨~도착지점까지 계산 

    return (lbtodt == -1 || lbtodt == 0) ? -1 : sttolb + lbtodt;
}

회전하는 숫자들을 저장한 뒤 회전시켜주고 그 중에서 최솟값을 정답에 저장해두면 된다.

회전하는 함수 rotate에서 기억해두어야 할 점은 

정방향 반복자(begin()과 end())를 사용했다면, rotate 함수는 왼쪽 회전을 수행하고

역방향 반복자(rbegin과 rend)를 사용하여 rotate를 사용하는 이유는 nums 벡터에 대해 오른쪽 회전을 수행하기 위해서 이다. 

#include <string>
#include <vector>
#include <algorithm>
int board[101][101];
using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    int cnt = 1;
    for (int i = 1; i <= rows; i++) {           //숫자판 초기화
        for (int j = 1; j <= columns; j++) {
            board[i][j] = cnt;
            cnt++;
        }
    }
    for (int i = 0; i < queries.size(); i++) {
        vector<int> nums;           //돌릴 숫자를 저장
        vector<pair<int, int>> xy;   //숫자들의 좌표값을 저장
        int mn = 1e9;
        int sty = queries[i][0];      //시작,끝 좌표
        int stx = queries[i][1];
        int edy = queries[i][2];
        int edx = queries[i][3];
        //도는 순서대로 숫자저장 오른->아래->왼->위
        //오른
        for (int x = stx + 1; x <= edx; x++) {
            nums.push_back(board[sty][x]);
            mn = min(mn, board[sty][x]);
            xy.push_back({ sty,x });
        }
        //아래
        for (int y = sty + 1; y <= edy; y++) {
            nums.push_back(board[y][edx]);
            mn = min(mn, board[y][edx]);
            xy.push_back({ y,edx });
        }
        //왼
        for (int x = edx - 1; x >= stx; x--) {
            nums.push_back(board[edy][x]);
            mn = min(mn, board[edy][x]);
            xy.push_back({ edy,x });
        }
        //위
        for (int y = edy - 1; y >= sty; y--) {
            nums.push_back(board[y][stx]);
            mn = min(mn, board[y][stx]);
            xy.push_back({ y,stx });
        }
        rotate(nums.rbegin(), nums.rbegin() + 1, nums.rend());          //시계방향 회전

        for (int x = 0; x < xy.size(); x++) {
            board[xy[x].first][xy[x].second] = nums[x];                 //회전한 벡터를 자리마다 대입
        }

        answer.push_back(mn);                               //최소값 저장
    }

    return answer;
}

연산자로 만들 수 있는 모든 순열에서 절댓값이 가장 큰 것을 찾아내면 되는 문제이다. 

과정은 

1. 숫자와 연산자를 나누어서 저장

2. 연산자의 우선순위를 순열로 뽑아주는 next_permutation 함수를 사용

3. 연산자의 우선순위에 따라 연산 후 max를 통해 비교 

※next_permutation 함수는 정렬된 벡터에 대해 사용해주어야 온전한 순열 조합들을 다 구할 수 있다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long cal(long long a,long long b,char c){
    if(c=='-') return a-b;
    else if(c=='+') return a+b;
    return a*b;
}
long long solution(string expression) {
    long long answer = 0;
    vector<long long>nums;          //숫자를 저장할 벡터
    vector<char> operators;         //연산자를 저장할 벡터
    vector<char> oper={'+','-','*'};
    sort(oper.begin(),oper.end());
    string tmp="";
    for(int i=0;i<expression.size();i++){           //숫자 및 연산자 저장 
        if(isdigit(expression[i])){
            tmp+=expression[i];
        }else{
            nums.push_back(stoll(tmp));
            operators.push_back(expression[i]);
            tmp="";
        }
    }
    nums.push_back(stoll(tmp));
    
     do{
         vector<long long> nsum(nums);               //합을 저장할 벡터
         vector<char>operTmp(operators);            //저장된 연산자
         for(int i=0;i<3;i++){
             for(int j=0;j<operTmp.size();){
                 if(oper[i]==operTmp[j]){
                     long long csum=cal(nsum[j],nsum[j+1],operTmp[j]);
                     nsum.erase(nsum.begin()+j,nsum.begin()+j+2);      //연산한 두 숫자 제거
                     operTmp.erase(operTmp.begin()+j);              //연산자 삭제
                     nsum.insert(nsum.begin()+j,csum);               //숫자를 제거한 자리에 합 넣어주기
                 }else{
                     j++;                           //연산자 우선순위가 아닐경우에만 다음 연산자로 넘어가게
                 }
             }        
         }
         answer=max(answer,abs(nsum[0]));
     }while(next_permutation(oper.begin(), oper.end()));
    
    return answer;
}

문제에서 푸는 방법을 알려줬으니 구현을 잘하면 되는 문제이다. 

나는 올바른 괄호 문자열을 검사하는 함수를 짜는 것과 나누는 것을 어떻게 해야할지 고민을 많이 해본 문제이다. 

올바른 괄호 문자열을 검사하는 함수는 stack을 사용해서 구현하고 

문자열을 u,v로 나누는 것은 괄호의 개수를 검사하여 나누면 된다.

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

using namespace std;
//올바른 괄호 문자열 검사
bool check(string s){
    stack<char> st;
    
    for(auto c:s){
        if(c=='(') st.push(c);                  
        else{
            if(st.empty())return false;
            st.pop();
        }
    }
    
    return st.empty();
}
string solution(string p) {
    string answer = "";
    if(p=="") return "";
    
    string u="",v="";
    int left=0,right=0;
    
    for(int i=0;i<p.length();i++){          //괄호의 갯수 검사
        if(p[i]=='(') left++;
        else right++;
        
        if(left==right){                //만약 괄호의 개수가 같다면 균형잡힌 괄호 문자열
            u=p.substr(0,i+1);
            v=p.substr(i+1);
            break;
        }
    }
    if(check(u))answer=u+solution(v);           //나눈 문자열에서 u가 올바른 문자열인지 확인
    else{
        answer='('+solution(v)+')';             //4-1~4-3
        
        for(int i=1;i<u.length()-1;i++){            //4-4 앞 뒤로 ()를 붙였으니 1~ len-1까지 
            answer+=u[i]=='('?')':'(';              //3항연산자로 ( 이면 )로 바꾸고 아니면 (로 바꿔주기
        }
    }
    
    
    return answer;
}

설명이 긴데 잘 읽어보면 핵심은 한 그룹의 최대공약수로 다른 그룹의 모든 수를 나눌 수 없는 값을 찾는 것이다 만약 그룹 별로 조건을 만족하는 값이 하나씩 나온다면 그 중 큰 값을 정답으로 한다.

#include <string>
#include <vector>
#include <algorithm>
//핵심 : 한그룹의 최대공약수로 다른 그룹을 나눴을 때 안 나눠지는게 있는가
using namespace std;
int gcd(int a, int b) {               //최대공약수 구하기
    if (b == 0) return a;
    return gcd(b, a % b);
}
int solution(vector<int> arrayA, vector<int> arrayB) {
    int answer = 0;
    int cur = arrayA[0];
    for (int i = 1; i < arrayA.size(); i++) {
        cur = gcd(cur, arrayA[i]);
        if (cur == 1) break;
    }
    if (cur != 1) {
        int cnt;
        for (cnt = 0; cnt < arrayB.size(); cnt++) {
            if (arrayB[cnt] % cur == 0) break;
        }
        if (cnt == arrayB.size()) answer = cur;
    }

    cur = arrayB[0];
    for (int i = 1; i < arrayB.size(); i++) {
        cur = gcd(cur, arrayB[i]);
        if (cur == 1) break;
    }
    if (cur != 1) {
        int cnt;
        for (cnt = 0; cnt < arrayA.size(); cnt++) {
            if (arrayA[cnt] % cur == 0) break;
        }
        if (cnt == arrayA.size()) answer = max(cur, answer);        //만약 두 그룹 다 조건에 만족하는 수가 있다면 그 중에 큰 수가 정답
    }
    return answer;
}