프로그래밍

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/60061

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

[풀이]
3차원 배열 map[202][202][2]를 선언하여
map[x][y][0] == true 이면 (x,y)~(x,y+1) 기둥이 설치된 것
map[x][y][1] == true 이면 (x,y)~(x+1,y) 보가 설치된 것
위와 같이 관리하도록 하였습니다.

이제 기둥과 보를 각각 설치할때 이것을 설치할 수 있는지와
제거할 때 제거할 수 있는지를 체크해야 합니다.

설치하는 할때 확인하는 것은 쉽습니다.
기둥의 경우 바닥인지, 아래 기둥이 있는지, 보가 있는지만 확인하면 설치가 가능하고
보의 경우 아래 기둥이 있는지, 양옆에 보가 있는지만 확인하면 됩니다.

하지만 제거할 때는 문제가 복잡해질 수도 있습니다.
특정 위치 (x,y)의 기둥이나 보를 제거한다고 할때,
"(x+b,y+b)에 기둥이나 보가 있으니까 (x,y)를 제거하면 안돼" 이렇게 생각하면 복잡해 지는 경우입니다.
단순하게
"(x,y)의 기둥(보) 를 지웠음에도 map의 모든 기둥과 보가 조건을 만족하고 있다면 (x,y)는 지워도 되겠네"
라고 생각하는 것이 좋습니다.

즉, (x,y)의 기둥(보)를 지워보고 nxn map의 모든 기둥봐 보를 2중 for문으로 체크해보면서 조건을 여전히 만족하는지를 체크하는 것입니다.

쿼리가 1000개이고 n이 최대 100이기 때문에 O(100x100x10000) 으로 충분히 시간내에 해결이 가능합니다.
만약 n이 좀더 큰수라면 지워야하는 (x,y)의 주변에 영향을 받을만한 (x+b,y+b)들만 체크해야 겠지만
n이 작아 생각할 필요가 없기 때문에 전체 점을 체크하였습니다.

(x,y) 위치의 기둥은 checkFunc[0](x,y), 보는 checkFunc[1](x,y) 로 체크할 수 있도록
lamda list를 만들었습니다 (0,1로 연결지을 수 있도록)

check 함수는 전체 점을 체크하는 함수입니다. 이곳에서 checkFunc를 사용하여 (x,y)를 제거했을 때 전체 점이
여전히 조건을 만족하면 true 아니면 false를 return합니다.

입력받은 x,y에 1씩 더하여 map을 +1,+1씩 평행이동 시켰다고 생각하고 풀면 index 범위 체크를 하지 않아도 됩니다.

var map = Array(202){Array(202){BooleanArray(2)}}
var checkFunc = listOf(
    {x:Int,y:Int -> y==1 || map[x][y-1][0] || map[x-1][y][1] || map[x][y][1]},
    {x:Int,y:Int -> (map[x-1][y][1] && map[x+1][y][1]) || map[x][y-1][0] || map[x+1][y-1][0] }
)
fun check(x:Int,y:Int,n:Int):Boolean{
    for(i in 1..n+1)
        for(j in 1..n+1){
            if(map[i][j][0] && !checkFunc[0](i,j)) return false
            if(map[i][j][1] && !checkFunc[1](i,j)) return false
        }
   return true
}
class Solution {
    fun solution(n: Int, build_frame: Array<IntArray>): Array<IntArray> {
        for((tx,ty,a,b) in build_frame){
            var x = tx+1
            var y = ty+1
            if(b==0){
                map[x][y][a]=false
                if(!check(x,y,n)) map[x][y][a]=true
            }else{
                if(checkFunc[a](x,y)) {
                    map[x][y][a]=true
                }
            }
        }
        var lst = mutableListOf<IntArray>()
        for(i in 1..n+1){
            for(j in 1..n+1){
                if(map[i][j][0]) lst.add(intArrayOf(i-1,j-1,0))
                if(map[i][j][1]) lst.add(intArrayOf(i-1,j-1,1))
            }
        }
        return lst.toTypedArray()
    }
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/기둥과_보_설치.cpp

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

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

[풀이]
n 1개로 무조건 n을 만들 수 있기 때문에 answer의 값은 1부터 시작합니다.
1~n-1을 순회하면서 i+(i+1)+(i+2)... 값을 만들어보면서 n이 넘어가면 break,
n이 나오면 answer에 1을 추가하고 break 하는식으로 답을 구해가면 됩니다.

n이 10000이고 i가 1인 경우에도
1+2+3+4.... = (n*(n+1))/2 = 10000 (등차수열 공식)
을 만족하려면 더하는 횟수인 n이 대충 계산해도 150도 넘을 수 없다는 것을 알 수 있습니다.
그러므로 시간복잡도는 O(10000*150) 정도로 시간내에 해결이 가능합니다.

#include <string>
#include <vector>
using namespace std;
int solution(int n) {
    int answer=1;
    for(int i=1;i<n;i++){ 
        bool ok=0;
        int sum=i,cur=i;
        while(sum<n){
            sum+=++cur;
            if(sum==n){
                answer++;
                break;
            }
        }
    }
    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/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/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