프로그래밍

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

[난이도] level2
[유형] 분할정복

[풀이]
정사각형의 수가 모두 같지 않다면 4개로 분할된 정사각형을 다시 검사하도록
재귀함수를 호출해주고 모두 같다면 0,1인지에 따라 개수를 1개 더해줍니다.

#include <string>
#include <vector>
using namespace std;
vector<int> answer(2);
vector<vector<int>> arr;
int same(int y,int x,int n){
    int t = arr[y][x];
    for(int i=y;i<y+n;i++)
        for(int j=x;j<x+n;j++)
            if(t!=arr[i][j]) return -1;
    return t;
}
void sol(int y,int x,int n){
    int ret = same(y,x,n);
    if(ret!=-1){
        answer[ret]++;
        return;
    }    
    int b = n/2;
    sol(y,x,b);
    sol(y+b,x,b);
    sol(y,x+b,b);
    sol(y+b,x+b,b);
}

vector<int> solution(vector<vector<int>> _arr) {
    arr=_arr;
    sol(0,0,arr.size());
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/쿼드압축 후 개수 세기.cpp

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

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

[풀이]
0의 개수를 직접 빼서 남은 1의 개수로
다음 string을 만들면서 1이 될때까지 반복하면 됩니다.

#include <string>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
using ll = long long;
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(auto num : numbers){
        ll ret=0;
        int sz = log(num)/log(2)+2;
        if(num==0) sz=1;
        int idx;
        for(int i=0;i<sz;i++){
            if((num&(1LL<<i))==0) {
                idx=i;
                break;
            }
        }
        ret=num+(1LL<<(idx));
        if(idx>0) ret-=1LL<<(idx-1);
        answer.push_back(ret);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/이진 변환 반복하기.cpp

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

[난이도] level2
[유형] 비트

[풀이]

1) 2진수로 표현했을 때 낮은 bit부터 확인하면서 0이 최초로 등장하는 index를 찾습니다.

2) 찾은 idx는 1로 바꿔주고 idx-1의 1은 0으로 바꿔주면 그 값이 조건을 만족하는 값입니다.
만약 0110 식으로 idx가 0이라면 0만 1로 바꿔주면 됩니다.

비트연산시 오버플로우가 날 수 있기 때문에 1LL<<idx와 같이 LL을 반드시 붙혀줘야 합니다.

#include <string>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
using ll = long long;
vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    for(auto num : numbers){
        ll ret=0;
        int sz = log(num)/log(2)+2;
        if(num==0) sz=1;
        int idx;
        for(int i=0;i<sz;i++){
            if((num&(1LL<<i))==0) {
                idx=i;
                break;
            }
        }
        ret=num+(1LL<<(idx));
        if(idx>0) ret-=1LL<<(idx-1);
        answer.push_back(ret);
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/2개 이하로 다른 비트.cpp

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

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

[풀이]
정삼각형이 아닌 직삼각형을 2차원 배열에 표시한다고 생각하면 편합니다.
삼각형의 안쪽으로 들어갈수록 삼각형은 변의 길이가 3씩 줄어들기 때문에 n부터 시작해서
변의 길이를 3씩 줄여가며 큰 삼각형에서 작은 삼격으로 배열에 표기를 해나갑니다.
y=1,x=1부터 시작해서 ↓ → ↖ 순으로 좌표를 움직여 가면서 숫자를 표기해주면 됩니다.

#include <string>
#include <vector>
using namespace std;
int map[1001][1001];
vector<int> solution(int n) {
    vector<int> answer;
    int y=1,x=1,k=0;
    for(int i=n;i>=1;i-=3){
        map[y][x]=++k;       
        for(int j=0;j<i-1;j++) map[++y][x]=++k;
        for(int j=0;j<i-1;j++) map[y][++x]=++k;
        for(int j=0;j<i-2;j++) map[--y][--x]=++k;
        y++;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            answer.push_back(map[i][j]);   
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/삼각 달팽이.cpp

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

[난이도] level2
[유형] 스택

[풀이]
전형적인 스택 문제입니다.

#include <string>
#include <vector>
#include <list>
#include <stack>
using namespace std;
list<char> li;

bool check(){
    stack<char> st;
    for(auto c : li){
        if(c=='['||c=='{'||c=='(') st.push(c);
        else {
            if(st.empty()) return 0;
            if(c==']'){
                if(st.top()!='[') return 0;
            }
            if(c=='}'){
                if(st.top()!='{') return 0;
            }            
            if(c==')'){
                if(st.top()!='(') return 0;
            }        
            st.pop();
        }
    }
    return st.empty();
}

int solution(string s) {
    int ans=0; 
    for(char c : s) li.push_back(c);

    for(int i=0;i<s.size();i++){
        ans+=check();

        li.push_back(li.front());
        li.pop_front();
    }

    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/괄호 회전하기.cpp

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

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

[풀이]
칼럼의 수 N이 8개, 로우가 20개이므로 모든 키의 조합에 대해 확인해봐도 시간내에 해결이 가능합니다.
N이 8이기때문에 bit연산을 이용하였습니다.
예를들어 0101이 후보키라면 0111은 최소성을 만족하지 못하므로 후보키가 될 수 없다는 것을 이용하였습니다.

1) 1~(2^N-1) 까지 키의 조합이 될 수 있는 모든 경우를 돌면서
몇개의 속성을 사용하는지에 따라 각각의 bitmasks 배열에 넣어줍니다.
ex) 11010 이라면 3개를 사용하므로 bitmasks[3]에 push
개수별로 나눠서 저장하는 이유는 bitmasks[1]부터 속성을 적게 사용하는 것부터 candidates로 분류해놔야
많은 속성을 사용하는 것들이 최소성을 만족하는지 체크할 수가 있습니다.
(다른 풀이를 보니 개수별로 분류하지 않고 1~2^N-1까지 순서대로 체크해도 문제가 없다는 것을 알 수 있었습니다. 예를들면 10101 10001보다 무조건 뒤에 오기 때문입니다.)

2) 가장 작은 속성을 사용하는 bitmasks[1] vector의 값들부터 순회하면서
현재 나온 값이 후보키가 될 수 있는지를 체크합니다.

[최소성 체크]
isExist() 함수는 이미 앞에 나온 후보키들에 의해 현재 확인중인 비트마스크가 후보키가 될 수 있는지를 체크합니다. 만약 현재 체크하는 값이 10101인데 후보키를 저장하는 cand에 10001이 들어있다면 isExist는
true를 return하며 종료합니다.
10101과 10001의 bit and 연산으로 간단히 포함관계인지 체크할 수 있습니다.
(10101 & 10001) == 10001 -> bit 연산 후에도 10001의 값을 유지한다는 것은 모든 bit가 현재 체크하는 값에서
살아있다는 의미이므로 이 둘은 포함관계입니다.

[유일성 체크]
isExist()가 false라면 그다음엔 현재 체크중인 bitmask로 유일성을 만족하는지 체크해야 합니다.
check() 함수에서 모든 relation을 순회하면서 masking된 속성의 string을 전부 이어붙힙니다.
주의할점이 그냥 이어붙히면 [A,AA] [AA,A]를 동일하게 인식하므로 "#"를 속성 뒤에 붙혀서 구분을 해주었습니다.
완성된 string을 set에 넣습니다. 만약 이미 string이 들어있다면 유일성을 만족하지 못하는 것이므로 false를 return 합니다.

3. 위 과정에서 !isExist() && check()를 만족하는 것들만 후보키로 등록되게 되며 이 개수를 return하면 정답입니다.

#include <string>
#include <vector>
#include <cstdio>
#include <set>
using namespace std;
int N;
vector<int> bitmasks[9],cand;
vector<vector<string>> relation;
bool check(int bitmask){
    set<string> s;
    vector<int> flag(9);
    for(int i=0;i<N;i++){
        if(bitmask&(1<<i)) flag[i]=1;
    }
    for(auto rel : relation){
        string tmp;
        for(int i=0;i<N;i++){
            if(flag[i]) tmp+=(rel[i]+"#");
        }
        if(s.find(tmp)!=s.end()) return false;
        s.insert(tmp);
    }
    return true;
}
bool isExist(int bm){
    for(auto v : cand){
        if(v == (v&bm)) return true;   
    }
    return false;
}
int solution(vector<vector<string>> _relation) {
    relation=_relation;
    int answer = 0;
    N=relation[0].size();

    for(int i=1;i<(1<<N);i++){
        int cnt=0;
        for(int j=0;j<N;j++){
            if((i&(1<<j))>0) cnt++;
        }
        bitmasks[cnt].push_back(i);
    }
    for(int i=1;i<=N;i++){
        for(auto bm : bitmasks[i]){
            if(!isExist(bm)){
                if(check(bm)) {
                    cand.push_back(bm);
                    answer++;
                }
            }
        }
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/후보키.cpp

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

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

[풀이]
당연히 그냥 구현 문제일줄 알았는데 info의 범위가 50000 query의 범위가 100000이나 되기 때문에
쿼리마다 모든 info를 확인하는 O(query*info)의 시간복잡도로는 효율성 테스트 통과가 불가능합니다.

지원자의 4가지 항목을 4자리 수로 변환해주는 Hashing과
어떤 점수를 넘는 지원자를 찾기 위한 binary search를 사용해주면 문제를 해결할 수 있습니다.

1) 아래와 같이 4가지 항목으로 숫자로 변환해주는 map 테이블을 만듭니다.
cpp, java, python => 1,2,3
backend, frontend => 1,2
junior, senior => 1,2
chicken, pizza => 1,2

2) 지원자의 정보 string을 분리하여 hash값을 만든 뒤 map> 타입의 map에
형태로 저장합니다. ex) mp["1111"].push_back(150)
그 뒤 map을 순회하면서 vector들을 정렬해줍니다. (binary search를 사용하기 위함입니다.)

3) query를 순회하면서 string을 쪼개서 만들 수 있는 모든 hash를 만들어줍니다.
저는 vector 4개를 선언하여 "-" 가 아닌 경우에는 그에 맞는 string의 변환값을 넣어주었고,
"-"인 경우에는 1,2 (언어의 경우 3까지) 모두 되므로 모두 vector에 넣어준 뒤
4중 for문을 돌려서 만들 수 있는 모든 hash를 만들어주었습니다.
query가 -,-,-,- 이어도 최대 3x2x2x2=24개 이기때문에 많은 시간이 들지 않습니다.

각 2)에서 저장한 hash key에 맞는 점수들이 저장되어있는 vector를 map에서 가져와
binary search를 통해 조건을 만족하는 가장 적은 점수의 지원자의 iterator를 가져옵니다.
mp[key].end()-it를 통해 조건을 만족하는 모든 지원자를 구할 수 있습니다.
이 값을 cnt 변수에 카운트해주면 최종 cnt 값이 현재 query의 정답입니다.

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

map<string,string> table;

vector<string> split(string s,string splitter){
    vector<string> ret;
    s+=splitter;
    int idx;
    while((idx=s.find(splitter)) != string::npos){
        string tmp = s.substr(0,idx);
        ret.push_back(tmp);
        //cout << tmp << '\n';
        s=s.substr(idx+splitter.size());
    }    
    return ret;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;

    table["cpp"]="1",table["java"]="2",table["python"]="3";
    table["backend"]="1",table["frontend"]="2";
    table["junior"]="1",table["senior"]="2";
    table["chicken"]="1",table["pizza"]="2";

    map<string,vector<int>> mp;
    for(auto s : info) {
        auto v = split(s," ");
        string hash;
        for(int i=0;i<v.size()-1;i++){
            hash+=table[v[i]];
        }
        mp[hash].push_back(stoi(v.back()));
    }
    for(auto& p : mp){
        sort(p.second.begin(),p.second.end());
    }

    int qnum=0;
    for(auto q : query){
        vector<string> sq = split(q," and ");
        vector<string> b = split(sq.back()," ");
        sq.pop_back();
        sq.insert(sq.end(),b.begin(),b.end());

        vector<string> v[4];

        for(int i=0;i<4;i++){
            if(sq[i]!="-") v[i] = {table[sq[i]]};
            else {
                v[i] = {"1","2"};
                if(i==0) v[i].push_back("3");
            }
        }

        int cnt=0;
        for(auto c1 : v[0]){
            for(auto c2 : v[1]){
                for(auto c3 : v[2]){
                    for(auto c4: v[3]){
                        string key = c1+c2+c3+c4;
                        int target=stoi(sq[4]);
                        auto it = lower_bound(mp[key].begin(),mp[key].end(),target);
                        cnt+=mp[key].end()-it;
                    }
                }
            }
        }
        answer.push_back(cnt);

    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/순위 검색.cpp

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

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

[풀이]
순수 구현 문제입니다.
모든 order를 정렬 뒤에 순회하면서 비트마스크를 이용해
모든 요리 코스 조합이 몇개 존재하는지 map에 저장하였습니다.
mp["코스"]=등장한 개수 (mp["AB"]=2) 와 같이 저장됩니다.

그 뒤 courses 배열을 순회하면서
코스에 포함된 요리 개수가 courses[i] 이면서 등장한 코스의 개수가 2개 이상인 것들을
vector에 <등장한 개수,"코스"> 형식으로 저장 한 뒤 오름차순으로 정렬합니다.

vector에서 등장한 개수가 큰 코스들은 answer vector에 저장해주면 됩니다.

모든 courses를 확인 후

answer를 정렬해주면 최종 정답입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
#include <cstdio>
using namespace std;
map<string,int> mp;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;

    for(auto& order : orders){
        sort(order.begin(),order.end());

        int sz = order.size();
        for(int i=0;i<(1<<sz);i++){

            vector<bool> flag(sz);
            string tmp;
            for(int j=0;j<sz;j++){
                if((i&(1<<j))>0) flag[j]=1;         
            }
            for(int j=0;j<sz;j++){
                if(flag[j]) tmp.push_back(order[j]);
            }
            if(tmp.size()>=2) {
                mp[tmp]++;
            }
        }
    }
    for(auto c : course){
        vector<pair<int,string>> v;
        for(auto& p : mp){
            if(p.first.size()==c && p.second>=2){
               v.push_back({-p.second,p.first});   
            }
        }
        if(v.empty()) continue;
        sort(v.begin(),v.end());

        int minV = v[0].first;
        for(auto& p : v){
            if(minV!=p.first) break;
            answer.push_back(p.second);
        }
    }
    sort(answer.begin(),answer.end());

    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/메뉴 리뉴얼.cpp