프로그래밍

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

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

[난이도] level3
[유형] 부분합

[풀이]
시간의 최대 길이가 N:100*60*60 정도에 logs의 크기가 M:300000 이므로
O(N*M) 알고리즘으로는 시간내에 해결이 불가능 합니다.
O(N) 혹은 O(M) 알고리즘을 생각해봐야 합니다.
NlogN을 생각하려면 정렬, 이분탐색 , set 등과 연관이 있어야 하는데 연관도가 떨어져 보입니다.

cnt[i] = 0~i까지 재생했을 때 총 누적 재생시간 (0<= i <= 나올 수 있는 최대 시간) 을 저장하는
cnt 배열을 만듦으로써 O(N+M)의 답을 구할 수 있습니다.

1)
일단 logs의 string을 초로 변환하여 start,end 타임을 구합니다.
sscanf(str.c_str(),"%d:%d:%d",&h,&m,&s) 와 같이 sscanf를 쓰면
형식이 정해진 string에서 필요한 정보를 쉽게 추출할 수 있습니다.

2)
구한 start,end를 이용해 cnt[start+1]++, cnt[end+1]-- 연산을 해주어
start와 end 지점에서 한 시청자의 재생이 시작,종료 되었음을 기록합니다.
+1을 해주는 이유는 start에서 재생이 시작 되었다면 start+1이 되서야 1초가 경과한 것이기 때문입니다.
마찬가지로 end일때도 end에 종료되면 end+1부터 종료가 된것이 영향이 있기 때문입니다.

3)
cnt[i]를 이용해 cnt[i]를 i초에 몇명의 시청자가 재생중인지를 기록하도록 할 것입니다.
for(int i=1;i<=pt;i++) cnt[i]+=cnt[i-1] 와 같이 누적합을 구해주면 됩니다.

4)
한번 더 위와 3)과 같이 누적해주면 cnt[i] = 0~i까지 재생했을 때 총 누적 재생시간 이 됩니다.
0~i까지 누적해서 더하기 때문에 위의 결과가 저장되는 것입니다.

5)
이제 어느 구간이 가장 누적 재생시간이 많이 나오는 지를 구해야 합니다.
cnt[i]-cnt[i-at] (at:adv_time <= i <= pt:play_time) 중 최댓값을 구하면서 그때의 i-at (시작 시간)을 구해줍니다.
이 값을 HH:MM:SS 형식으로 변환해주면 됩니다.

#include <string>
#include <vector>
using namespace std;
using ll = long long;
int pt,at;
ll cnt[400000];
int convert(string str){
    int h,m,s;
    sscanf(str.c_str(),"%d:%d:%d",&h,&m,&s);
    return h*3600+m*60+s;
}
string solution(string play_time, string adv_time, vector<string> logs) {

    pt=convert(play_time);
    at=convert(adv_time);

    vector<pair<int,int>> v;
    for(auto s : logs){
        int idx=s.find("-");
        int start=convert(s.substr(0,idx)), end=convert(s.substr(idx+1));
        cnt[start+1]++;
        cnt[end+1]--;
    }
    for(int j=0;j<2;j++)
        for(int i=1;i<=pt;i++) 
            cnt[i]+=cnt[i-1];

    ll mv=0;
    int t=0;
    for(int i=at;i<=pt;i++){
        if(mv<cnt[i]-cnt[i-at]){
            mv = cnt[i]-cnt[i-at];
            t=i-at;
        }
    }
    string rh=to_string(t/3600); 
    string rm=to_string((t%3600)/60);
    string rs=to_string((t%60));
    if(rh.size()<2) rh='0'+rh;
    if(rm.size()<2) rm='0'+rm;
    if(rs.size()<2) rs='0'+rs;
    string ret = rh+":"+rm+":"+rs;
    return ret;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/광고_삽입.cpp

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

[난이도] level3
[유형] Greedy

[풀이]

나올 수 있는 모든 110을 뽑아서 남은 문자열에서 가장 뒤에 있는 0 뒤에 모든 110을 붙혀주면 되는 문제입니다.

이게 가능한 이유는 문자열에 있는 존재하는 모든 110을 제거했다면,
1이 연속으로 2개 이상 나오는 경우는 "111111"과 같이 0이 존재하지 않는 경우밖에 없습니다.
왜냐하면 0이 붙는 순간 "110"이 되어 제거되기 때문입니다.

결국 남은 문자열은
1만 남은 경우 또는 "1001010"과 같이 1 다음에는 무조건 0이 나오는 형태 두가지 경우일 수밖에 없습니다.

1만 남은 경우에는 사전순으로 작은 문자가 되려면
110들을 문자열의 앞에다가 붙혀야 합니다. ex) "110110+11111"

1과 0이 같이 나오는 "10010100" 같은 경우에는
11이 연속으로 나오는 "110"을 무조건 맨 마지막 0 뒤에 넣어야 합니다.
앞쪽에 넣게 되면 연속된 "11"에 의해 사전순으로 뒤로 밀리게 되기 때문입니다.

위 두가지 케이스를 한번에 처리하기 위해 0을 남은 문자열 앞에 더해주었습니다.
이러면 마지막 0의 위치만 찾아서 제거한 "110"들을 넣기만 하면 됩니다.

#include <string>
#include <vector>
using namespace std;
string sol(string str){
    string ret,ans;
    int cnt=0;
    for(auto c : str){
        if(c=='0' && ret.size()>=2 && ret.substr(ret.size()-2,2)=="11"){            
            ret.pop_back();ret.pop_back();
            cnt++;
        } else ret.push_back(c);
    }
    ret='0'+ret;
    int idx;
    for(int i=ret.size()-1;i>=0;i--){
        if(ret[i]=='0') {
            idx=i;
            break;
        }
    }
    for(int i=0;i<=idx;i++) ans+=ret[i]; 
    while(cnt--) ans+="110";
    for(int i=idx+1;i<ret.size();i++) ans+=ret[i];
    return ans.substr(1);
}
vector<string> solution(vector<string> s) {
    vector<string> answer;
    for(auto str : s) answer.push_back(sol(str));
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/110_옮기기.cpp

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

[난이도] level3
[유형] Greedy

[풀이]
a배열의 최대 길이가 50만이기 때문에 한번 배열을 스캔하면서 최대 길이의 스타수열을 찾아야합니다.

"a의 모든 수는 0 이상 (a의 길이) 미만입니다."
위의 조건에 의해 나올 수 있는 수도 50만 미만이기 때문에 두개의 배열을 이용해 문제를 풀 수 있습니다.
cnt[500000],idx[500000] 두 배열을 선언하여

cnt[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 최대길이
idx[k] : 현재까지 확인된 숫자 k를 교집합으로 포함하는 스타 수열의 마지막 index

위와 같은 값을 저장하는 용도로 사용합니다.

이제 a배열을 0부터 순회하면서
i번째 원소를 확인중일 때, 조건을 만족한다면 cnt[a[i]], idx[a[i]]를 업데이트 할 수 있습니다.

i번째 원소의 왼쪽에 짝이 있는 경우와, 오른쪽에 짝이 있는 경우가 있을 수 있습니다.

왼쪽에 짝이 있으려면,
idx[a[i]] 즉, a[i]를 교집합으로 하는 스타 수열의 마지막 index보다는 i-1이 작아야하며 (idx[a[i]] < i-1)
a[i] != a[i-1]을 만족해야 합니다. (서로 값이 달라야 하기 때문에)

i-1만 검사해도 되는 이유는 만약 a[i] == a[i-1] 이고 a[i-1] != a[i-2] 라면 (예를 들어 a[i]가 1일때 [...2,1,1] 이런 형태)
idx[a[i]]가 i-1일 것이므로 idx[a[i]] < i-1 에서부터 조건을 만족하지 못하여 a[i] != a[i-1]는 검사할 필요가 없어집니다.

왼쪽에 짝이 있다면 i가 이제 마지막 index가 되므로 idx[a[i]]=i로 업데이트 해주고
짝이 한개 추가되었기 때문에 cnt[a[i]]++를 해주고 다음 index를 검사합니다.

만약 왼쪽에 짝이 없다면 오른쪽에 있는지 검사해야 합니다.
오른쪽에 a[j] != a[i] 를 만족하는 j가 있다면 idx[a[i]]=j 로 업데이트 해주면 됩니다.

for문을 돌때마다
먼저 if(i<=idx[a[i]]) continue 를 추가해줍니다.
위 조건에 걸렸다는 것은 스타 수열의 index가 i 뒤에 있다는 것이기 때문에 i는 스타 수열에 포함될 수 없어 검사할 필요가 없습니다.

최종적으로 cnt[i] (0<=i<(a의 길이)) 중에 최댓값을 구하고, 쌍의 개수이므로 그 값에 2배를 해주면 됩니다.

알고리즘 분류가 애매하지만 매 루프마다 최적의 index를 고르는 것이기 때문에 Greedy 문제로 생각됩니다.

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
const int mxN=5e5;
int cnt[mxN],idx[mxN],ans;
int solution(std::vector<int> a) {
    memset(idx,-1,sizeof(idx));
    for(int i=0;i<a.size();i++){
        if(i<=idx[a[i]]) continue;
        if(i>0&& idx[a[i]] < i-1 && a[i]!=a[i-1]){
            cnt[a[i]]++, idx[a[i]]=i;
            continue;
        }
        int j=i;
        while(++j<a.size() && a[j] == a[i]);
        if(j<a.size()) cnt[a[i]]++, idx[a[i]]=j;
    }
    for(int i=0;i<a.size();i++) ans=std::max(ans,cnt[i]);
    return ans*2;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/스타_수열.cpp

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

[난이도] level3
[유형] 브루트포스

[풀이]
board의 빈곳의 모양과, table의 조각의 모양을 각각 2차원 vector에 저장한 뒤 매칭시켜서 몇개나 매칭이 될 수 있는지 구하면 됩니다.
각 모양을 구할 때는 dfs를 이용하여 모양의 좌표들을 저장해주면서 상,하,좌,우 끝값의 좌표를 기록해줍니다.
이것을 알아야 모양의 행과 열과의 길이를 알 수 있고, 올바른 크기의 2차원 vector를 선언하여 좌표를 저장할 수 있습니다.
board 또는 table 중 한쪽의 모양들은 시계방향으로 회전시키며 4방향에 대한 모양을 따로 저장해야 합니다.
아래 코드에서는 vector<vvi> shapes[4],shapes_tb 를 선언하여 shapes에는 빈칸 모양의 4방향 vector를, shapes_tb에는 table의 조각 모양 vector를 저장하였습니다.
4방향을 구할 때는 시계방향으로 90도 돌린 vector를 반환하는 함수를 한개만 선언하면 연속적으로 돌려주면서 4방향을 모두 구할 수 있습니다.

시간 복잡도는 최악의 경우 O((4*50*50)*(50*50)) 정도 나오는것으로 보여 시간내에 AC를 받는 것이 가능합니다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
using vvi=vector<vector<int>>;
const int dy[4]={-1,1,0,0}, dx[4]={0,0,1,-1}, inf = 9e8;
vector<vvi> shapes[4],shapes_tb;
bool visit[50][50];
int N,l,r,u,d,scnt,ans;
vector<pair<int,int>> p;
void init(){
    u=l=inf;
    d=r=-inf;
    p.clear();    
}
vvi rotate(vvi& org){
    int r = org[0].size();
    int c = org.size();
    vvi ret = vvi(r,vector<int>(c));

    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            ret[i][j]=org[c-j-1][i];

    return ret;
}
void dfs(int y,int x,int k,vvi& b){
    visit[y][x]=1;
    p.push_back({y,x});
    l=min(l,x),r=max(r,x);
    u=min(u,y),d=max(d,y);

    for(int i=0;i<4;i++){
        int ny=y+dy[i],  nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=N||b[ny][nx]!=k||visit[ny][nx]) continue;
        dfs(ny,nx,k,b);
    }
}
int match(vvi& a,vvi& b){
    if(a.size()!=b.size() || a[0].size() != b[0].size()) return -1;
    int ret=0;
    for(int i=0;i<a.size();i++)
        for(int j=0;j<a[0].size();j++){
            if(a[i][j]+b[i][j]!=1) return -1; 
            ret+=a[i][j];
        }
    return ret;
}
int solution(vvi board,vvi table) {

    N=board.size();
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(!board[i][j] && !visit[i][j]){
                init();
                dfs(i,j,0,board);
                int row = d-u+1, col = r-l+1;
                vvi shape = vvi(row,vector<int>(col,1));
                for(auto& v : p) shape[v.first-u][v.second-l]=0;

                for(int k=0;k<4;k++){
                    shapes[k].push_back(shape);
                    shape=rotate(shape);
                }
            }
        }
    }
    memset(visit,0,sizeof(visit));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(table[i][j] && !visit[i][j]){
                init();
                dfs(i,j,1,table);
                int row = d-u+1, col = r-l+1;
                vvi shape = vvi(row,vector<int>(col,0));
                for(auto& v : p) shape[v.first-u][v.second-l]=1;
                shapes_tb.push_back(shape);
            }
        }
    }
    vector<bool> filled(shapes[0].size());
    for(auto stb : shapes_tb){
        for(int i=0;i<shapes[0].size();i++){
            if(filled[i]) continue;
            bool ok=false;
            for(int j=0;j<4;j++){
                int ret = match(stb,shapes[j][i]);
                if(ret!=-1){
                    ok=true;
                    ans+=ret;
                    filled[i]=true;
                    break;
                }
            }
            if(ok) break;
        }
    }
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/위클리_챌린지_3주차.cpp