프로그래밍

https://programmers.co.kr/learn/courses/30/lessons/12984

[난이도] level4
[유형] 누적합

[풀이]
N*N의 최대가 300*300이기 때문에 모든 땅을 같은 높이로 맞춰보는 방법은 (300*300)^2 연산으로
O(N^4)의 시간복잡도를 필요로 하기 때문에 사용이 불가능합니다.

하지만 누적합 배열을 이용하면 쉽게 O(N^2) 으로 해결이 가능합니다.

1) 우선 2차원 land 배열을 1차원 배열 arr[90001]로 옮긴 뒤 정렬해줍니다.
   이제 N=N*N으로 바꿔줍니다.

2) sum[90001] 배열을 누적합을 저장합니다.

3) 최적의 높이는 arr[1] 또는 arr[2] ... arr[N] 입니다. 이 이외의 높이로 맞추는 것은
   비용을 더 늘어나게 합니다.
   그러므로 arr[i]의 각 높이로 맞춰보면서 비용이 최소가 될때를 찾으면 됩니다.

   예를 들어 N=6이고 각 땅의 높이가 [3,3,4,4,5,7] 일때 아래 그림을 참고해봅시다.
   (N은 k^2 꼴이여야 하지만 편의상 6으로 설정하였습니다.)

   높이를 arr[3]=4로 맞추고 싶을 때, 좌측의 4보다 높이가 작은 땅은 파란색 영역 만큼
   높이를 증가시켜야 하고, 우측의 높이가 4보다 높은 땅은 초록색 영역만큼 높이를 줄여야 합니다.
   이는 누적합 배열 sum을 이용해 아래와 같이 계산이 가능합니다.

   좌측 파란색 영역 =
   [높이가 arr[i]이고 넓이가 i-1인 직사각형 : arr[i]*(i-1)]  -  [1~(i-1)까지 땅 높이의 합 : sum[i-1]]
    = arr[i]*(i-1)-sum[i-1]

   우측 초록색 영역 =
   [i~N까지 땅 높이의 합 : sum[N]-sum[i-1]] - [높이가 arr[i]이고 넓이가 (N-(i-1))인 직사각형 : arr[i]*(N-(i-1))]
    = arr[i]*(i-1)-sum[i-1]

   좌측 값만큼 블록을 추가해야 하므로 P를 곱하고, 우측 값만큼 블록을 제거해야 하므로 Q를 곱한 뒤
   두 값을 더하면 최종 비용을 구할 수 있습니다.

   i:1~N 의 모든 값에 대해 위의 연산은 해주며 최소 비용을 구하면 최종 답을 구할 수 있습니다.
   (arr[i]가 동일한 땅들은 가장 앞에 있는 땅만 계산해주면 됩니다.)

파라메트릭 서치를 이용한 풀이도 있지만 위의 풀이가 좀 더 직관적이고 코드가 간결합니다.

#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
ll arr[90001],sum[90001],ans=-1;
int N;
ll solution(vector<vector<int> > land, int P, int Q) {
    N=land.size();
    int idx=1;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            arr[idx++]=land[i][j];
    N*=N;
    sort(arr,arr+N+1);
    for(int i=1;i<=N;i++) sum[i]=sum[i-1]+arr[i]; 
    int cur=-1;
    for(int i=1;i<=N;i++){
        if(arr[i]==cur) continue;
        cur=arr[i];
        ll v=0;
        v+=(sum[N]-sum[i-1]-arr[i]*(N-(i-1)))*Q;
        v+=(arr[i]*(i-1)-sum[i-1])*P;
        if(ans==-1 || ans > v) ans=v;
    }
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/지형_편집.cpp

https://programmers.co.kr/learn/courses/30/lessons/12920

[난이도] level4
[유형] 이분탐색

[풀이]
어떤 코어에서 일의 처리가 완료될때마다 그 코어에 새로운 작업을 할당해주고,
나머지 코어의 일의 남은 시간을 업데이트 하는 방식을 생각할 수 있는데 이런 방식으로는
코어의 개수 N이 10000, 처리해야할 일의 개수가 50000개 이므로 O(N*M)이 되어 시간내에
해결할 수가 없습니다.

이런 유형의 문제에는 이분탐색(파라메트릭 서치)를 이용해야 합니다.

최저시간 low=-1, 최고시간 high=200000로 두고
어떤 시간 mid가 지났을 때, 처리한 총 일의 개수 cnt를 기준으로 low 혹은 high를 mid로 업데이트해줍니다.

(코어의 수가 2개, 각각의 처리시간은 10000, 총 일의 개수가 50000일때가 시간이 가장 오래 걸리는 케이스입니다.
이때 모든 일을 처리하는데 (10000*50000)/2 시간이 걸리는데 high을 200000 정도로만 잡아도 통과를 합니다.
TC가 부족한 것 같습니다.)

처리한 총 일의 개수는 (mid(시간)/cores[i])+1 들의 합으로 구할 수 있습니다.
예를 들어 일 한개를 처리하는데 2시간이 걸리는 코어의 일처리 과정을 시간별로 보면
아래와 같이 (현재 시간을 코어의 처리시간으로 나눴을 때의 몫)+1 으로 표현됩니다.

0시간 : 1개
1시간 : 1개
2시간 : 2개
3시간 : 2게
4시간 : 3개
5시간 : 3게
6시간 : 4개
7시간 : 4개
....

이 때 목표 처리 물건 개수 n보다 적게 만드는 시간 중에 최고 시간이 lo로 수렴하도록 해야합니다.
이렇게 하면 lo+1 시간에 어떤 코어 i에 물건을 할당하면 최종적으로 n개를 처리할 수 있기 때문입니다.
0번 코어부터 N-1번 코어부터 확인하면서 lo+1 시간에 물건을 할당할 수 있는지를 검사해서 할당할 수 있으면
lo시간까지 처리한 물건의 개수에 1개씩 더해줍니다.
(lo+1)%cores[i]==0 을 만족하면 lo+1시간에 물건 할당이 가능하다는 것을 위의 일처리 과정 예시를 보면 확인할 수 있습니다.

lo가 -1로 나온 경우는 처리해야할 일의 개수가 코어 개수보다 적은 것이므로 n번째 일을 처리하는 n번 코어를 리턴해주기만 하면 됩니다.

이런 유형의 문제를 이분탐색으로 처리할 생각을 하기가 쉽지는 않지만 꽤 자주 보이는 전형적인 유형이므로
익혀두면 도움이 될 것 같습니다.

#include <vector>
#include <cstdio>
using namespace std;
int solution(int n, vector<int> cores) {
    int lo=-1,hi=2e5,mid=0;
    while(lo+1<hi){
        mid = (lo+hi)/2;
        int cnt=cores.size();
        if(mid>0) for(int i=0;i<cores.size();i++) cnt+=mid/cores[i];
        if(cnt<n) lo=mid;
        else hi=mid;
    }
    if(lo==-1) return n;
    int cnt=cores.size();
    for(int i=0;i<cores.size();i++) cnt+=lo/cores[i];
    for(int i=0;i<cores.size();i++){
        if((lo+1)%cores[i]==0) cnt++;
        if(cnt==n) return i+1;
    }
    return 0;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/선입_선출_스케줄링.cpp

https://programmers.co.kr/learn/courses/30/lessons/67260

[난이도] level4
[유형] 그래프

[풀이]
우선 주어진 path로 인접 리스트를 만들었습니다. 풀이 중 필요없는 간선은 지워줄 것이기 때문에
vector가 아닌 set을 이용하였습니다.

order를 이용해 각 노드를 방문하려면 어떤 노드를 먼저 방문해야 하는지를 par 배열에 저장하였습니다.

풀이는 아래와 같습니다.

root부터 dfs를 돌리며 방문할 수 있는 노드 i를 방문하고 visit[i]=true 체크를 해줍니다.
방문할 수 없는 노드는 먼저 방문해야 하는 노드가 아직 방문하지 않은 상태로, visit[par[i]]==false인 상태입니다.
이 경우는 방문을 하지 않고 false를 return 해줍니다.

만약 모든 자식 노드들의 dfs 함수가 true를 return 했다면 모든 자식을 방문한 것이므로 현재 노드는 더이상 확인할 필요가 없습니다. 그러므로 인접 리스트로 사용되는 set에서 현재 노드와 부모 노드의 간선을 끊어줍니다.
위 제거 과정을 해주지 않으면 반복되는 dfs에 의해 시간 초과가 발생합니다.

이렇게 한 시행을 완료하였으면 새롭게 visit된 노드의 개수를 total에 더해줍니다.
만약 새롭게 visit된 노드가 있다면 이 노드가 visit되지 않아 이전 시행에서 방문하지 못했던 노드들도 이제 방문이 가능해진 것이기 때문에 다시 root부터 dfs를 돌리며 같은 시행을 반복합니다.

만약 visit된 노드 개수가 0이라면 더 이상 방문이 불가능하여 모든 노드를 방문할 수 없는 상태이므로 최종답으로 false를 return 합니다.

모든 노드를 방문해서 total==n 이 된다면 최종답으로 true를 return 해주면 됩니다.

#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
bool visit[200001];
set<int> adj[200001];
int par[200001],cnt,total;
bool sol(int prv, int n){
    if(par[n]!=-1 && !visit[par[n]]) return 0;
    if(!visit[n]) cnt++;
    visit[n]=1;
    bool ret=1;
    for(int nxt : adj[n]){
        if(nxt!=prv && !sol(n,nxt)) ret=0;
    }
    if(ret && n!=0) {
        adj[prv].erase(n);
        adj[n].erase(prv);
    }
    return ret;
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    memset(par,-1,sizeof(par));
    for(auto& p : path) adj[p[0]].insert(p[1]), adj[p[1]].insert(p[0]);
    for(auto& o : order) par[o[1]]=o[0];
    while(1){
        cnt=0;
        sol(-1,0);
        if(cnt==0) return 0;
        total+=cnt;
        if(total==n) return 1;
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/[카카오_인턴]_동굴_탐험.cpp

※ 아래 링크의 카카오에서 제공하는 공식 풀이는 방향 그래프의 cycle 판별을 이용한 풀이입니다.
https://tech.kakao.com/2020/07/01/2020-internship-test/

cycle을 활용한 풀이 코드는 아래와 같습니다.

#include <vector>
using namespace std;
bool visit[200001],finished[200001];
vector<int> tadj[200001],adj[200001];
void dfs(int prv,int n){
    for(auto nxt : tadj[n]){
        if(prv!=nxt) {
            adj[nxt].push_back(n);
            dfs(n,nxt);
        }
    }
}
bool dfs2(int n){
    visit[n]=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]){
            if(!dfs2(nxt)) return 0;
        }else if(!finished[nxt]) return 0;
    }
    finished[n]=1;
    return 1;
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order) {
    for(auto& p : path) tadj[p[0]].push_back(p[1]), tadj[p[1]].push_back(p[0]);
    dfs(-1,0);
    for(auto& o : order) adj[o[1]].push_back(o[0]);
    for(int i=0;i<n;i++) if(!visit[i] && !dfs2(i)) return 0;
    return 1;
}

https://programmers.co.kr/learn/courses/30/lessons/49995

[난이도] level4
[유형] 이분탐색

[풀이]
N이 2000이므로 O(N^3)까지 가게되면 시간초과가 납니다.
O(N^2)이나 O(N^2logN) 알고리즘이 필요합니다.

아래 코드는 부분합+이분탐색을 이용하여 O(N^2logN) 으로 해결하였습니다.
다른 분들은 보통 투포인터를 이용한 O(N^2)으로 푼것 같습니다.

풀이는 일단 구간합 배열을 만들고 시작합니다.
sum[i] : 1~N까지 모든 원소들의 합.

그 뒤 첫번째 아들이 선택할 수 있는 모든 구간 (i~j)에 대해 둘째 아들이 선택할 수 있는 (j+1~k)가 있는지를 구할 것입니다.

구간합 배열을 이용해 sum(i,j)는 sum[j]-sum[i-1]로 구할 수 있습니다.
이제 sum[j]-sum[i-1]와 동일한 값을 같는 sum(j+1,k)를 찾아야 하는데 lower_bound(이분탐색)를 이용해 찾을 수 있습니다.

부분합 배열에서 sum(j+1,k)가 존재하는지를 찾으려면 sum[j] + sum[j] - sum[i-1] 을 lower_bound를 이용해서 찾으면 됩니다.

위의 식이 나온 이유는 아래와 같습니다.

        첫째아들   둘째아들
1+2+...[i+..+j] / [(j+1)+..+k] = sum(j+1,k)
                     [i+..+j]       = sum(i,j)

위와 같이 sum(j+1,k)와 sum(i,j)가 같아야 하기 때문에 1~j까지의 합 sum[j]에 sum(j+1,k) 인 (sum[j] - sum[i-1])를 더한 값이 부분합 배열에 존재하면 sum(j+1,k) == sum(i,j) 가 만족되어 각 아들이 가진 과자 수 sum[j] - sum[i-1]가 정답의 후보가 될 수 있습니다.

이 후보들을 이용해 최댓값을 갱신해 주면 최종 답을 구할 수 있습니다.

#include <vector>
#include <algorithm>
using namespace std;
int N,answer;
int solution(vector<int> cookie) {
    N=cookie.size();
    cookie.insert(cookie.begin(),0);
    vector<int> sum(N+1);
    for(int i=1;i<=N;i++) sum[i]=sum[i-1]+cookie[i];
    for(int i=1;i<=N-1;i++){
        for(int j=i;j<=N-1;j++){
            int t = 2*sum[j]-sum[i-1];
            int idx = lower_bound(sum.begin(),sum.end(),t)-sum.begin();
            if(idx<=N && sum[idx]==t) answer=max(sum[j]-sum[i-1],answer);
        }  
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/쿠키_구입.cpp

https://programmers.co.kr/learn/courses/30/lessons/42894

[난이도] level4
[유형] 구현

[풀이]
N제한이 200으로 여유롭기 때문에 효율적인 알고리즘 보다는 구현능력을 묻는 문제입니다.

아래 코드에서는 map<int,vector<pair<int,int>>> 타입의 block,empt(y) map을 선언하여
block에는 key색상 블록 4개의 좌표를, empty에는 key색상 블록이 직사각형이 되기 위해 채워줘야 하는 좌표 2개를 저장하기로 하였습니다.

block을 구하는 것은 board를 한번 순회하면서 block[board[y][x]].push_back({y,x})와 같이 간단하게 구할 수 있지만,
empty를 구하는 방법은 여러가지가 있을 수 있는데 시간 제한이 여유롭기 때문에 가장 단순한 방법으로 구하였습니다.

각 종류의 블록마다 board를 (0,0) ~ (N-1,N-1) 까지 순회하면서 2x3,3x2 모양을 모든 점에서 확인하는 방식입니다.
예를들어 숫자가 K인 블록의 empty를 찾고 싶을 때, 2x3, 3x2 모양의 모든 직사각형을 확인하면서 K가 적혀있는 점이 4개 있는 곳의 나머지 2개의 점이 K의 empty 블록들입니다.

empty를 구하였다면 while문을 돌면서 지울 수 있는 블록들을 더이상 지울 수 없을때까지 지워주면 됩니다.
empty인 블록 2개 모두 다른 블록의 방해를 받지 않고 보드의 가장 위인 (-1,x)에 도달하면 해당 종류의 블록은 지울 수 있는 것입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
int dy1[6]={0,0,0,1,1,1};
int dx1[6]={0,1,2,0,1,2};
int dy2[6]={0,1,2,0,1,2};
int dx2[6]={0,0,0,1,1,1};
int N;
map<int,vector<pair<int,int>>> block,empt;
vector<vector<int>> board;
bool check(int c,vector<pair<int,int>> v){
    for(auto [y,x] : v){
        while(y>=0){
            if(board[y--][x]!=0) return 0;
        }
    }
    for(auto [y,x] : block[c]) board[y][x]=0;
    return 1;
}
int solution(vector<vector<int>> _board) {
    int answer = 0;
    board=_board;
    N=board.size();
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) 
            if(board[i][j]>0) block[board[i][j]].push_back({i,j});

    for(auto [v,mp] : block){
        for(int i=0;i<N-1;i++){
            for(int j=0;j<N-2;j++){
                vector<pair<int,int>> tmp;
                int cnt=0;
                for(int d=0;d<6;d++){
                    int ny=i+dy1[d];
                    int nx=j+dx1[d];
                    if(board[ny][nx]==v) cnt++;
                    else tmp.push_back({ny,nx});
                }
                if(cnt==4) empt[v]=tmp;
            }
        }
    }
    for(auto [v,mp] : block){
        for(int i=0;i<N-2;i++){
            for(int j=0;j<N-1;j++){
                vector<pair<int,int>> tmp;
                int cnt=0;
                for(int d=0;d<6;d++){
                    int ny=i+dy2[d];
                    int nx=j+dx2[d];
                    if(board[ny][nx]!=v) tmp.push_back({ny,nx});
                    else cnt++;
                }
                if(cnt==4) empt[v]=tmp;
            }
        }
    }
    bool ok=1;
    vector<bool> erased(201,0);
    while(ok){
        ok=0;
        for(auto [c,v] : empt){
            if(erased[c]) continue;
            if(check(c,v)){
                erased[c]=1;
                ok=1;    
                answer++;
            }
        }
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/블록게임.cpp

https://programmers.co.kr/learn/courses/30/lessons/43236

[난이도] level4
[유형] 이분탐색

[풀이]
바위가 최대 50000개이기 때문에 이중 n개를 고른 모든 경우를 해보면 시간초과가 발생합니다.

distance가 최대 10억 이하인데 이렇게 큰 수가 주어진 경우 이분탐색을 의심해볼 수 있습니다.

1) rocks 는 오름차순으로 정렬해줍니다.
2) low를 0 high를 distance+1로 놓습니다.

3) 매 탐색에서 나오는 mid를 이용해
   "바위들간의 가장 가까운 거리는 기껏해야 mid이다"
   이렇게 정의를 하면 0 -> rocks[0] -> rocks[1]... 순으로 방문할 때
   rocks[j]-rocks[i]의 거리가 mid보다 멀면 rocks[j]는 제거된 바위로 간주하면 됩니다.

   i) 남아있는 바위의 개수가 rocks.size()-n (남아있어야할 바위의 개수) 보다 크다면,
   mid를 조금 더 큰 수를 사용해볼 수 있기 때문에 mid=lo 로 업데이트 하고 다음 시행으로 넘어갑니다.
   (잘 생각해보면 mid가 커질수록 남아있는 바위의 수는 적어지고,
   mid가 작아질수록 남아있는 바위의 수는 커지기 때문입니다.)

   ii) 남아있는 바위의 개수가 rocks.size()-n보다 더 적다면
   바위를 더 남겨야합니다. 그러려면 mid를 더 줄여서 더 간격이 좁은 바위도 포함될 수 있도록 해야합니다.
   hi=mid로 업데이트 해주고 다음 시행으로 넘어갑니다.

   위의 시행을 반복하다보면 lo와 hi가 1 차이가 나는 상황까지 수렴하게 됩니다.
   이때의 lo 값이 최적의 값이므로 이 값을 return하면 됩니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
    sort(rocks.begin(),rocks.end());
    int lo=0, hi=distance+1;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        int cnt=0;
        int cur=0;
        for(int i=0;i<rocks.size();i++){
            if(rocks[i]-cur>=mid) {
                cnt++;
                cur=rocks[i];
            }
        }
        if(cnt>=rocks.size()-n) lo=mid;
        else hi=mid;
    }
    return lo;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/징검다리.cpp

https://programmers.co.kr/learn/courses/30/lessons/84325

[난이도] level1
[유형] 구현

[풀이]
단순 구현 문제입니다.

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
map<string,map<string,int>> mp;
void split(string str){
    vector<string> ret;
    int idx;
    str+=' ';
    while((idx=str.find(' '))!=string::npos){
        ret.push_back(str.substr(0,idx));
        str=str.substr(idx+1);
    }
    map<string,int> m;
    for(int i=1;i<=5;i++){
        m[ret[i]]=6-i;
    }
    mp[ret[0]]=m;
}
string solution(vector<string> table, vector<string> languages, vector<int> preference) {
    string answer = "";
    for(auto t : table) split(t);
    int mv=0;
    for(auto p : mp){
        auto job = p.first;
        auto tb = p.second;
        int v=0;

        for(int i=0;i<languages.size();i++) v+=preference[i]*tb[languages[i]];
        if(v>mv){
            answer = job;
            mv=v;
        }
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level1/직업군_추천하기.cpp

https://programmers.co.kr/learn/courses/30/lessons/1830

[난이도] level3
[유형] 구현

[풀이]
규칙1을 만족하는 모든 부분문자열을 찾고 규칙2를 만족하는 모든 부분문자열을 찾는 방식으로
문자열을 여기저기 뒤지면서 찾는 방법으로 접근했다가 풀이에 실패했던 문제입니다.

위와 같이 풀게 되면 예외 케이스도 너무 많이 생기게 되고 원본 문자열을 복구하는데도 어려움이 있습니다.

더 쉬운 방법은 index 0부터 시작하는 valid한 부분문자열 떼어내기를 반복하며, 만약 0부터 시작해서 valid한 부분문자열이 없다면 invalid를 return해주는 방식입니다.

항상 0번 문자을 포함하는 valid한 부분문자열을 구하면 됩니다.

0번 문자 sentence[0]이 소문자인 경우와 대문자인 경우로 나눠주고 시작합니다.

i) sentence[0]이 소문자인 경우
rule2가 적용되어야 합니다. aXXXXa 혹은 aBcBcBa와 같은 두가지 형태가 있을 수 있습니다.

    1) vector에 sentence[0]이랑 같은 문자를 가지고 있는 index들을 저장합니다.
    2) vector의 크기는 반드시 2여야 합니다. 아니면 invalid를 return합니다.
    3) vector의 두 index 사이의 문자열이 aXXXXa,aBcBcBa 둘중 한가지 형태가 맞는지 확인해야 합니다.
       이를 위해 rule1 함수와 allUpper 함수를 정의하였습니다.

       (※문제의 지문에서 규칙2를 적용한 것이지만 코드를 작성하다보니 함수명을 rule1로 하였습니다.)
       rule1 함수는 전달된 string이 rule2의 형태 (BcBcB) 인지 확인해서 맞으면 원본 string(BBB) 를 return하고
       아닌 경우 "-1"을 return합니다.
       주의할 점이 (B) 형태는 rule1을 만족하지 않아야 합니다. 저는 소문자 포함유무를 ok flag를 통해 체크해서 걸러냈         습니다.

       allUpper 함수는 전달된 string이 (XXXX) 형태인지를 체크합니다.

       먼저 rule1인지 체크하고 "-1"을 return 했다면 allUpper를 체크합니다 이것도 역시 "-1"이라면
       invalid한것이므로 "invalid"를 최종 return합니다.

       rule1 혹은 allUpper를 만족했다면 return된 string을 answer에 추가해주고
       sentence에서 확인 부분까지 제거하고 다음 시행으로 넘어갑니다.

       이때 소문자는 한번밖에 사용 못하는 규칙이 있기 때문에 used[26] vector에 소문자를 사용할때마다 소문자를 사용 했는지를 체크해줘야 합니다.

ii) sentence[0]이 대문자인 경우

    ii-1) AAAAx...와 같이 sentence[1]도 대문자인 경우
        sentence[0]은 무조건 떼어내서 answer에 추가해주고
        다음 시행으로 넘어가면 됩니다. 원본 문자에 공백이 있었다고 가정하면 되기 때문에 붙어있는 대문자들은 한개씩
        떼어낼 수 있습니다.

    ii-2) AbB...와 같이 sentence[1]이 소문자인 경우
        sentence[1]과 같은 모든 index들을 vector에 담아준 뒤 이것의 개수에 따라 다르게 처리해줍니다.

        ii-2-1) vector의 크기가 2가 아닌 경우
            크기가 1인 경우 AbB, 3이상인 경우 AbBbBbBbC 형태일수밖에 없으므로 위에서 사용한 

            rule1을 만족하는지 체크합니다.
            만족하면 answer에 추가하고 다음 시행으로 넘어갑니다.

        ii-2-2) vector의 크기가 2인 경우
            AbBbA 형태이거나, AbBBBBBBbC 형태일 수 있습니다.
            AbBbA도 A bBb A 형태로 쪼개면 후자의 형태와 같이 볼 수 있고,
            후자의 형태로 최대한 자르는 것이 더 유리합니다.

            그러므로 sentence[0]만 잘라서 answer에 추가해주고 다음 시행으로 넘어갑니다.
            이러면 자연스럽게 sentence[1]은 소문자였으므로 i)케이스 가게 됩니다.

위의 과정을 sentence가 empty가 될때까지 반복하면 최종 답을 얻을 수 있습니다.

#include <string>
#include <cctype>
#include <vector>
#include <iostream>
using namespace std;
const string ivd = "invalid";
string rule1(string str){
    string ret;
    if(str.size()<3) return "-1";
    char c = str[1];
    bool ok=0;
    for(int i=0;i<str.size();i++){
        if(islower(str[i])) ok=1;
        if(i%2==0){
            if(islower(str[i])) return "-1";
            ret+=str[i];
        }else{
            if(c!=str[i]) return "-1";
        }
    }
    if(!ok) return "-1";
    return ret;
}
string allUpper(string str){
    string ret;
    for(auto c : str){
        if(!isupper(c)) return "-1";
        ret+=c;
    }
    return ret;
}
string solution(string sentence) {
    vector<bool> used(26,0);
    string answer = "";
    int it=0;
    while(!sentence.empty()){
        string ret;
        vector<int> pos;
        if(islower(sentence[0])){
            if(used[sentence[0]-'a']) return ivd;
            used[sentence[0]-'a']=1;
            for(int i=0;i<sentence.size();i++){
                if(sentence[i]==sentence[0]) {
                    pos.push_back(i);
                }
            }
            if(pos.size()!=2) return ivd;

            string center = sentence.substr(1,pos.back()-1);
            if(center=="") return ivd;
            ret = rule1(center);
            string target;
            if(ret=="-1") {
                ret=allUpper(center);
                if(ret=="-1"){
                    return ivd;
                }
            }else{
                if(used[sentence[2]-'a']) return ivd;
                used[sentence[2]-'a']=1;
            }
            sentence = sentence.substr(pos.back()+1);
        }else{
            if(sentence.size()==1 || isupper(sentence[1])){
                ret=sentence[0];
                sentence=sentence.substr(1);
            }else{
                for(int i=0;i<sentence.size();i++){
                    if(sentence[1]==sentence[i]) pos.push_back(i); 
                }

                if(pos.size()!=2){
                    if(pos.back()==sentence.size()-1) return ivd;
                    if(islower(sentence[pos.back()+1])) return ivd;
                    string center = sentence.substr(0,pos.back()+2);
                    ret=rule1(center);
                    if(ret=="-1") return ivd;
                    if(used[sentence[1]-'a']) return ivd;
                    used[sentence[1]-'a']=1;
                    sentence=sentence.substr(pos.back()+2);
                }else{
                    ret=sentence[0];
                    sentence=sentence.substr(1);
                }   
            }
        }
        answer+=ret+" ";
    }
    answer.pop_back();
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/브라이언의_고민.cpp