코딩생존기

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

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

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

정렬후에 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;
}

이번 문제도 문제설명이 길어서 잘 읽어야한다. 

문제는 손님이 주문한 단품메뉴들을 가지고 가능한 조합을 모두 만든 다음

손님이 주문한 횟수만큼 해당 메뉴의 카운트를 증가 시켜주고

2명 이상이 주문한 메뉴 중에 코스에 들어갈 음식의 개수와 맞으면서가장 많이 선택된 음식이 조건에 부합한다면 저장해 주면 된다.

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

unordered_map<string,int>m;     //조합한 메뉴 저장할 맵

void dfs(int idx,string tmp,string order){
    if(tmp.size()>order.size()){
        return;
    }
    m[tmp]++;
    for(int i=idx;i<order.size();i++){
        dfs(i+1,tmp+order[i],order);
    }
}

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(auto order : orders){
        sort(order.begin(),order.end());
        dfs(0,"",order);                //조합할 수 있는 모든 메뉴 저장
    }
    for(auto cours : course){
        int mostOrdered=0;
        for(auto menu:m){
            if(menu.first.size()==cours){       //코스의 개수를 만족하면서 가장 많이 선택된 횟수 선택
                mostOrdered=max(mostOrdered,menu.second);
            }
        }
        if(mostOrdered<=1)continue;             //만약 2명 이상의 손님에게 주문된 구성이 아닐 때
        for(auto menu : m){
            if(menu.first.size()==cours&&menu.second==mostOrdered){
                answer.push_back(menu.first);           //조건에 부합한다면 저장
            }
        }
    }
    sort(answer.begin(),answer.end());
    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;
}

문제 설명을 잘 읽어야한다.

m: 기억한 멜로디 music: 방송된 곡 정보 정답 : 일치하는 음악

핵심은 방송된 곡 정보가 기억하고있는 멜로디패턴에 있는지를 확인해야한다. 

1단계로 #붙은것도 1초로 인식하니 1글자 영단어로 바꿔준다.

2단계로 곡이 재생된 방송시간과 곡의 길이를 가져온다.

재생된 방송시간보다 곡의 길이가 길 경우는 중간에 자르고 짧을 경우는 반복한다. 

그렇게 만들어진 음악에 기억한 멜로디 패턴이 있다면 answer로 지정해준다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
//m: 기억한 멜로디 music: 방송된 곡 정보 정답 : 일치하는 음악 
//핵심 : 방송된 곡 정보가 기억하고있는 멜로디패턴에 있는지
string change(string& m, map<string, char>& s) {               //#붙은 음들 바꿔주기
    string out = "";
    for (int i = 0; i < m.size(); i++) {
        if (m[i + 1] == '#') {
            out += s[m.substr(i, 2)];
            i++;
        }
        else {
            out += m[i];
        }
    }
    return out;
}

string solution(string m, vector<string> musicinfos) {
    string answer = "(None)";
    int aHour = 0, bHour = 0, aMin = 0, bMin = 0, time = 0, btime = 0;
    string melody = "", title = "";
    map<string, char> s;

    s["C#"] = 'c';
    s["D#"] = 'd';
    s["F#"] = 'f';
    s["G#"] = 'g';
    s["A#"] = 'a';

    melody = change(m, s);

    for (int i = 0; i < musicinfos.size(); i++) {
        string tmp = "", music = "";

        aHour = stoi(musicinfos[i].substr(0, 2)) * 60;
        aMin = stoi(musicinfos[i].substr(3, 2));
        bHour = stoi(musicinfos[i].substr(6, 2)) * 60;
        bMin = stoi(musicinfos[i].substr(9, 2));
        time = (bHour + bMin) - (aHour + aMin);     //나중시간- 전 시간

        for (int j = 12; j < musicinfos[i].size(); j++) { //곡 제목부터
            if (musicinfos[i][j] == ',') {
                title = musicinfos[i].substr(12, j - 12);
                tmp = musicinfos[i].substr(j + 1);             //곡의 음 패턴
                break;
            }
        }
        music = change(tmp, s);
        if (music.size() < time)            //재생시간이 곡 시간보다 클경우 반복
        {
            tmp = music;

            for (int j = 1; j < time / tmp.size(); j++)
                music += tmp;
            for (int j = 0; j < time % tmp.size(); j++)
                music += tmp[j];
        }
        else                //곡시간보다 재생시간이 짧으면 자르기
            music = music.substr(0, time);

        if (music.find(melody) != string::npos) {
            if (btime < time) {
                answer = title;
                btime = time;
            }
        }
    }
    return answer;
}

반시계 방향으로 달팽이 채우기를 진행한 결과를 1차원 벡터로 반환해줘야한다.

반시계 방향으로 진행할때 총 3단계를 거친다

1. 아래로 이동

2. 오른쪽으로 이동

3. 위로 이동

일단 2차원벡터를 0으로 초기화시켜둔 다음 진행한다.

1단계 : 아래로 이동

아래로 이동에서 고려해야할 점은 단계가 진행될 수록 열과 끝나는 부분이 달라야한다는 점이다

열은 증가해야하고 끝나는 부분을 줄어들어야한다.

그리고 다 이동하고 나서는 오른쪽으로 이동할 위치를 지정해주기 위해 

2단계 : 오른쪽으로 이동

2단계에서 고려해야할 점은 행과 끝나는 범위의 열이다.

열은 전에 했던 부분에서 1 증가값에서 시작해서  채워진부분 전까지 진행하고

행은 단계별로 감소해야한다.

3단계 : 위쪽으로 이동

3단계에서 고려해야할 점은  끝나는 범위의 행과 열이다.

행은 이전값의 하나 전 인덱스에서 채워진 인덱스앞까지이고

열은 단계별로 감소해야한다.

구현을 잘 해야하는 문제인데 이해하기가 정말 어려웠다. 쓰고나서도 어려운 문제라 여러번 다시 봐야겠다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n) {
    vector<int> answer;
    vector<vector<int>> triangle;
    
    if(n==1){
        answer.push_back(1);
        return answer;
    }
    
    for(int i=1;i<=n;i++){              //트라이앵글 모양 잡아주기
        vector<int>tmp;
        for(int j=0;j<i;j++) tmp.push_back(0);
        triangle.push_back(tmp);
    }
    
    int col=0,row=0;
    int num=1;
    int turn=0;                 //turn 한단계가 끝날수록 증가 -> 값이 들어갈 수 있는 곳 범위, 전체-turn 반복횟수
    while(true) {
        if (triangle[col][row] > 0) break;          //만약 채워져있는 칸이라면 끝
        
        for(int i=col;i<n-turn;i++){            //아래로 이동 
            if(triangle[i][turn]==0){
                triangle[i][turn]=num++;
                col=i; row=turn;
            }else break;
        }
        row+=1; turn+=1;        //채워져있는 거 다음 부분부터 
        
        for(int j=row;j<=n-turn;j++){            //오른쪽으로 이동 
            if(triangle[n-turn][j]==0){             //
                triangle[n-turn][j]=num++;
                col=n-turn; row=j;
            }else break;
        }
        col-=1;         //채워져있는거 이전 부터
        
        for(int k=col;k>=turn;k--){         //끝~채워진거 앞까지 위로
            if(triangle[k][k-turn+1]==0){              //k~1번째 까지
                triangle[k][k-turn+1]=num++;
                col=k; row=k-turn+1;
            }else break;
        }
        col+=1;
    }
    
    for(int i=0;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size();j++) answer.push_back(triangle[i][j]);
    }
    return answer;
}

1로 구성된 가장 큰 정사각형을 찾는 문제이다. 

정사각형의 넓이가 2이상일때 자신의 왼쪽, 위, 왼쪽 대각선위가 모두 1이상이여야하며 이때 하나라도 0이라면 정사각형이 될 수 없다. 

2*2 정사각형을 보자면 오른쪽 아래를 기준으로 보자면 자신의 왼쪽, 위, 왼쪽 대각선위가 모두 1이여야 한다. 그렇게 생각해보자면 오른쪽 아래의 값이 2가 될 수 있다.

3*3을 보자면 자신의 왼쪽, 위, 왼쪽 대각선위가 모두 2여야 한다. 이때 오른쪽 아래의 값은 선분의 길이인 3이 된다.

이론을 이해하기 어려웠지만 익숙해지면 쉽게 풀 수 있을 것같다.

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

int solution(vector<vector<int>> board)
{
    int answer = board[0][0];
    for (int i = 1; i < board.size(); i++) {
        for (int j = 1; j < board[i].size(); j++) {
            if (board[i][j] == 1) {
                board[i][j] = 1 + min({ board[i - 1][j],board[i][j - 1],board[i - 1][j - 1] });         //왼쪽,위,왼쪽 대각선 위
                answer = max(answer, board[i][j]);
            }
        }
    }
    return answer * answer;
}