Junnnho

programmers 수식 최대화 : programmers.co.kr/learn/courses/30/lessons/67257

2020 카카오 인턴십 문제에서 출제된 수식 최대화 입니다.

연산자의 우선순위를 강제하여 해결해야 하는데,

문자열을 다뤄야하며 이 문제에서는 범위가 커질수록 링크드리스트를 사용하는 것이

효율면에서는 좋을 것 같습니다.

저는 범위가 작아서 평소에 편하게 사용하는 배열만으로 문제를 해결하였습니다.

처음에 주어진 문자열을 숫자와 연산자로 구분지어준 후에

강제한 연산자 순서대로 계산해주시면 됩니다.

문자열에 나온 연산자가 무엇이 있는지 알 수 없기 때문에

무엇이 나왔는지 구분해주고 순서를 줘야된다고 생각할 수도 있는데,

아래 코드 중 calcluate 함수에서 처음에 for문을 0-2까지 3번 반복합니다.

3번 반복하면서 + - * 에 대한 문자열을 강제로 확인하기 때문에

solution 내부에 *-+ *+- .. 의 6가지 경우의 수를 사용한 것 처럼 해주셔도 문제를 해결하는데 문제없습니다.

단, 계산이 끝났으면 숫자를 담고있는 배열은 반드시 길이가 1이 되어야 계산이 완벽하게 된 것입니다.

또한 절대값 계산해주시는 것도 잊으시면 안됩니다.

코드에 주석으로 설명을 첨부하였으니 읽어보시면 될 것 같습니다.

#include <string>
#include <vector>
using ll = long long;
using namespace std;

ll answer = 0;

void calculate(vector<ll> number, vector<char> exp, string str){
    // 연산자 3개를 찾습니다. (i in 0~2)
    for(int i = 0; i<3; i++){
        for(int k = 0; k<exp.size(); k++){
            char ch = exp[k];
            if(ch == str[str.size()-1]){
                // erase 때문에 링크드리스트를 사용하시는 것이 효율면에서는 좋습니다.
                if(ch == '*'){
                    ll cal = number[k]*number[k+1];
                    number.erase(number.begin()+k+1);
                    number[k] = cal;
                    exp.erase(exp.begin()+k);
                }
                else if(ch == '+'){
                    ll cal = number[k]+number[k+1];
                    number.erase(number.begin()+k+1);
                    number[k] = cal;
                    exp.erase(exp.begin()+k);
                }
                else if(ch == '-'){
                    ll cal = number[k]-number[k+1];
                    number.erase(number.begin()+k+1);
                    number[k] = cal;
                    exp.erase(exp.begin()+k);
                }
                k--;
            }
        }
        //탐색한 연산자는 삭제해줍니다.
        str.pop_back();
    }
    
    // 계산이 끝났을 때 길이가 1이여야 완벽히 계산된 것입니다.
    if(number.size() == 1){
        answer = max(answer, abs(number[0]));
    }
    
}

long long solution(string expression) {
    
    vector<ll> number;
    vector<char> exp;
    int num = 0;
    // 숫자와 연산자를 구분해줍니다.
    for(int i = 0; i<expression.size(); i++){
        char ch = expression[i];
        if(ch >= '0' && ch <= '9') num = num*10 + (ch-'0');
        else{
            number.push_back(num);
            num = 0;
            exp.push_back(ch);
        }
    }
    // 마지막 숫자를 추가시켜줍니다.
    number.push_back(num);
    
    // 강제로 우선순위를 지정해줍니다.
    // 총 6가지의 경우의 수가 필요합니다.
    string chstring;
    chstring = "-+*";
    calculate(number, exp, chstring);
    chstring = "+-*";
    calculate(number, exp, chstring);
    chstring = "-*+";
    calculate(number, exp, chstring);
    chstring = "*-+";
    calculate(number, exp, chstring);
    chstring = "*+-";
    calculate(number, exp, chstring);
    chstring = "+*-";
    calculate(number, exp, chstring);
        
    return answer;
}

programmers 호텔 방 배정 : programmers.co.kr/learn/courses/30/lessons/64063

2019 카카오 개발자 겨울 인턴십, level4의 호텔 방 배정 문제입니다.

처음에는 set을 이용해서 방이 비어있는지 확인하고 없으면 +1씩 체크하는 방식으로 코딩하였습니다.

결과는 역시 정확도만 만점이고 효율성에서 나락되었습니다.

이걸 어떻게 해야할지 오래 고민해보았는데, 

+1씩 확인해야 하는 탐색과정을 줄이는게 가장 중요할 것 같았습니다.

그래서 만약 현재 사람이 원하는 방이 비어있다면

'그 방에 배정시키고,

만약 이 방을 다른 사람이 또 원하게 된다면 현재방의 +1 방에 바로 배정시키자' 로 접근했습니다.

여기서 중요한 것은 현재방의 +1 방이 또 배정되어있는 상태인가? 입니다.

결국 현재 배정한 방의 그 다음방이 '어디까지 배정되어 있는지'를 알아야 합니다.

+1씩 탐색하는 것은 첫 코딩때 set을 이용한 것과 같지만, 이를 계산해서 미리 알아둔다면

그 다음에는 또 같은 방에 대해서는 +1씩 탐색할 필요가 없으니 탐색시간을 줄일 수 있습니다.

map을 통해서 <현재 배정한 방, 그 다음방의 연결된 마지막 방> 의 형식으로 문제를 해결하였습니다.

#include <string>
#include <vector>
#include <map>
using namespace std;
using ll = long long;

map<ll, ll> visit;

ll findNextRoom(ll room){
    if(visit[room] == 0) return room; // 배정되어 있지 않은 room 방에 배정시킬 수 있습니다
    visit[room] = findNextRoom(visit[room]); // room 방이 어디까지 연결되어 있는지 탐색하는 동시에 연결시킵니다
    return visit[room];
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    for(auto room : room_number){
        if(visit[room] == 0){ // 배정되어있지 않다면
            answer.push_back(room); // 배정시키고
            visit[room] = findNextRoom(room+1); // +1 방이 어디까지 연결되어있는지 탐색합니다
        }
        else{ // 배정되어있다면
            ll nextRoom = findNextRoom(room+1); // +1 방이 어디까지 연결되어있는지 탐색합니다
            answer.push_back(nextRoom); // 찾아낸 방에 배정합니다
            visit[nextRoom] = findNextRoom(nextRoom+1); // 찾아낸 방의 +1 방이 어디까지 연결되어 있는지 탐색합니다
        }
    }
    
    return answer;
}

programmers 징검다리 건너기 : programmers.co.kr/learn/courses/30/lessons/64062

2019 카카오 개발자 겨울 인턴십 level3의 징검다리 건너기 문제입니다.

정확도와 효율성을 동시에 따지는 문제라는 것은 뭔가 알고리즘이 존재한다는 의미입니다.

정확성만 따지자면 2중 포문으로 k개에 대해서 모든 경우를 구하는 것인데,

징검다리의 수가 20만개에 원소의 값들은 2억이라서 효율성 점수를 얻는데는 실패할 것입니다.

저는 건널 수 있는 최대 값이 k라는 것에서 힌트를 얻어 이분탐색에 접근하였습니다.

현재 예시를 보겠습니다.

stones                                           k                                                 result

만약 친구 3명이 징검다리를 건넌다면? 

0 1 2 0 0 0 1 0 2 0 이라는 값이 됩니다.

0 0 0 이 3번 반복됩니다.

한번에 건너뛸 수 있는 k의 값이 3이라고 주어져 있습니다.

이는 인덱스2 부터는 3칸을 한번에 뛰어넘을 수 없다는 소리가 됩니다.

즉 => 3명까지는 징검다리를 건넜고, 4번째 친구부터는 징검다리를 못건넌다는 얘기입니다.

만약 친구 4명이 징검다리를 건넜다고 해도

3명이 건넜을 때 처럼

0 1 2 0 0 0.. 에서 0이 3번 반복되는 구간을 찾을 수 있습니다.

즉 0 이 k번 반복되는 구간이 있다는 것으로부터 저는 아래와 같은 생각을 하였습니다.

'현재 인원보다 많은 인원이 징검다리를 건널 수는 없다' 는 것이고

'현재 인원도 사실은! 징검다리를 건널 수 있는지 없는지는 모른다' 는 것이기 때문에 

'현재 인원이 일단 정답이라고 생각하고, 혹시 못 건널수도 있으니까 인원을 줄여보자!' 입니다.

코드는 아래와 같습니다.

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

bool checkCross(vector<int> stones, int k, int mid){
    
    int zero = 0;
    for(int i = 0; i<stones.size(); i++){
        int sub = stones[i] - mid;
        if(sub <= 0) zero++;
        else zero = 0;
        
        if(zero == k) return false;
    }
    
    return true;
}

int solution(vector<int> stones, int k) {
    
    int left = 1;
    int right = 200000000;
    int mid;
    while(left < right){
        mid = (left+right)/2;
        
        if(checkCross(stones, k, mid)){
            left = mid + 1;
        }
        else{
            right = mid; // 이 인원까지는 뛸 수 있을지 모른다. 줄여나가보자!
        }
    }
    
    return right;
}

programmers 불량 사용자 : programmers.co.kr/learn/courses/30/lessons/64064

2019 카카오 개발자 겨울 인턴십에 나온 불량 사용자 입니다.

dfs(backtraking)의 대표적인 문제입니다.

현재 어떤 userId가 banId될 수 있는지 유지하면서 dfs로 모든 userId를 banId와 비교하였습니다.

중요한 것은 답이 될 수 있는 banId가 모인 banList가 중복되면 안된다는 것입니다.

dfs를 인덱스 순으로 돌리기 때문에, banList에 push되는 userId는 '순서'가 유지될 것입니다.

이를 이용해서 banList의 사이즈가 ban 사이즈와 같아졌을 때 banList에 푸쉬된 스트링값들을 '따로 처리'해주면

쉽게 중복을 확인할 수 있습니다.

저는 '따로 처리'를 그냥 string 변수에 ' ' 간격으로 덧붙여서 문자열로 만든 후에

set을 이용해서 찾아낸 답이였는지 중복을 확인해주는 방법으로 문제를 해결하였습니다.

이는 현재 문제의 범위가 작아서 가능한 것이고

범위가 큰 문제에서는 스트링을 임의의 숫자같은 것으로 변경해주거나 등등의 방법으로 '따로 처리'를 할 수 있습니다.

#include <string>
#include <vector>
#include <iostream>
#include <set>
using namespace std;

vector<string> user;
vector<string> ban;
vector<string> banlist;
bool usingban[9];
int answer;
set<string> visit;

void dfs(int idx){
    if(banlist.size() == ban.size()){
        
        string visitid = "";
        for(auto i : banlist){
            visitid += i;
            visitid += ' ';
        }
        
        if(visit.find(visitid) == visit.end()){
            answer++;
            visit.insert(visitid);
        }
        
        return;
    }
    
    if(idx < user.size()){
        string user_id = user[idx];
        for(int i = 0; i<ban.size(); i++){
            if(usingban[i]) continue;
            string ban_id = ban[i];
            if(user_id.size() == ban_id.size()){
                bool checkban = true;
                for(int j = 0; j<ban_id.size(); j++){
                    if(ban_id[j] != '*' && (ban_id[j] != user_id[j])){
                        checkban = false;
                        break;
                    }
                }
                if(checkban){
                    usingban[i] = true;
                    banlist.push_back(user_id);
                    dfs(idx+1);
                    usingban[i] = false;
                    banlist.pop_back();
                }
            }
        }
        dfs(idx+1);
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    
    user = user_id;
    ban = banned_id;
    
    dfs(0);
    
    return answer;
}