프로그래밍

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

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

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

[풀이]
2차원 배열의 특정 부분을 회전하는 순수 구현 문제입니다.
저는 이런 문제에서 주로 배열보다는 복사가 쉬운 2차원 vector를 이용해
복사본 tmp를 만들어서 업데이트 해주는 방식으로 구현합니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
using vvi=vector<vector<int>>;
int N,M;
int rotate(int y1,int x1,int y2,int x2,vector<vector<int>>& map){
    int ret = 9e8;
    vvi tmp = map;

    for(int i=x1+1;i<=x2;i++) ret=min(ret,tmp[y1][i]=map[y1][i-1]);
    for(int i=y1+1;i<=y2;i++) ret=min(ret,tmp[i][x2]=map[i-1][x2]); 
    for(int i=x2-1;i>=x1;i--) ret=min(ret,tmp[y2][i]=map[y2][i+1]); 
    for(int i=y2-1;i>=y1;i--) ret=min(ret,tmp[i][x1]=map[i+1][x1]);
    map=tmp;
    return ret;
}
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    N=rows;
    M=columns;
    vvi map(N+1,vector<int>(M+1));
    int k=0;
    for(int y=1;y<=N;y++)
        for(int x=1;x<=M;x++)
            map[y][x] = ++k;
    for(auto v : queries) answer.push_back(rotate(v[0],v[1],v[2],v[3],map));
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/행렬 테두리 회전하기.cpp

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

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

[풀이]
방 한개의 칸이 5x5이기 때문에 (0,0)~(4,4) 부터 모든 점을 확인해도 시간내에 충분히 해결이 가능합니다.
만약 현재 점 (y,x)가 사람이고 아래의 P점이라면

K
K K K
K K P M M
M M M
M

M으로된 표시된 곳에 사람이 있으면서 파티션으로 막혀있지 않은지만 확인해주면 됩니다.
K로 된 곳은 이미 이전에 점을 확인하면서 체크가 되었기 때문에 확인할 필요가 없습니다.

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


bool inRange(int y,int x){
    return (y<5 && x<5 && y>=0 && x>=0);
}

bool check(int y,int x,vector<string>& map){

    if(map[y][x]!='P') return true;

    if(inRange(y+1,x) && map[y+1][x]=='P') return false;

    if(inRange(y,x+1) && map[y][x+1]=='P') return false;

    if(inRange(y+2,x) && map[y+2][x]=='P' && map[y+1][x]!='X') return false;

    if(inRange(y,x+2) && map[y][x+2]=='P' && map[y][x+1]!='X') return false;


    if(inRange(y+1,x+1) && map[y+1][x+1]=='P'){
        if(map[y+1][x]!='X') return false;
        if(map[y][x+1]!='X') return false;
    }
    if(inRange(y+1,x-1) && map[y+1][x-1]=='P'){
        if(map[y][x-1]!='X') return false;
        if(map[y+1][x]!='X') return false;        
    }
    return true;
}

bool checkMap(vector<string>& map){
    for(int y=0;y<5;y++){
        for(int x=0;x<5;x++){
                if(!check(y,x,map)) {
                    return false;
                }
        }
    }
    return true;
}


vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int i=0;i<5;i++){
        bool ret = checkMap(places[i]);
        if(!ret) answer.push_back(0);
        else answer.push_back(1);
    }


    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/거리두기 확인하기.cpp

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

https://github.com/has2/Algorithm/blob/master/programmers/level2/%ED%81%B0%20%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp