카카오 코테 2023 KAKAO BLIND RECRUITMENT 후기

나는 현역 취준생에서는 물러났지만, 아직 요건이 되어 참여하게 되었다. 결혼을 앞둔 32살이긴해도 .. 대학생느낌으로다가 캬캬

주관적 난이도 후기이다. 못 푼 건 좀 아쉽다. 4 솔

생각외로 시간을 많이 쓴 부분은 지문에 제약조건이 숨어있는 점이다. 코드포스에서는 제약조건 란에도 친절하게 있는데.. 카카오는 지문에 숨겨져있었다. 제약조건에 따라 문제 유형이 확확 달라지니까 ...
1번 문제 달력문제 "월의 일은 28일로", 3번 문제에서 할인율은 "10%, 20%, 30%, 40%"로 주어진다. 이 조건 때문에 코드를 수정해야하거나, 정답이 안 맞아서 굉장히 시간을 허비했다 총 합 한 50분 고생했다. 

그리고 4번 비트연산 때도 이제 머리가 굳어져서, mid = (f+t)/2 임을 찾아내지 못 해 시간을 25분 정도 썼던건 비밀.

생각외로 이번 알고리즘 느낌이 constructive 느낌인 듯 하다.

문제	주관적 난이도
1 30점	Codeforces div2. A
2 100점	Codeforces div2. B +
3 100점	Codeforces div2. B
4 150점	Codeforces div2. B +

1번문제 달력 ( 제약조건이 지문에 들어가있어서 약간 애매했음 )  (python) 

월마다 일자를 어떻게 처리해야할까 고민해서 relativedelta 라이브러리를 쓰려다가 custom library라 활용을 못 했다. 그것도 월은 28일로만 구성된다 라는 제약조건이 지문에 있어서, 필요가 없게 되었지만.

from datetime import datetime
from typing import Dict

def add_month(cur_date: datetime, month: int) -> datetime:
    cur_years = cur_date.year
    cur_month =  cur_date.month
    cur_day = cur_date.day
    cur_month += month
    cur_day -= 1
    if cur_day == 0:
        cur_day = 28
        cur_month -= 1
    cur_years += (cur_month-1)//12
    cur_month = ((cur_month-1)%12)+1
    return datetime(cur_years, cur_month, cur_day)

def solution(strtoday, strterms, strprivacies):
    tupled = list(map(lambda d: tuple(d.split(' ')), strterms))
    terms: Dict[str, int] = { tup[0] : int(tup[1]) for tup in tupled}

    today:datetime = datetime.strptime(strtoday, '%Y.%m.%d')

    privacies = list(map(lambda d: tuple(d.split(' ')), strprivacies))

    answer = []
    for idx, privacy in enumerate(privacies):
        strinsdate, term = privacy
        insdate = datetime.strptime(strinsdate, "%Y.%m.%d")
        expired_date = add_month(insdate, terms[term])
        if expired_date < today:
            answer.append(idx+1)

    return answer

# solution("2022.05.19", 1 , 2)
solution("2022.05.19", ["A 6", "B 12", "C 3"] , 
    ["2021.05.02 A", "2021.07.01 B", "2022.02.19 C", "2022.02.20 C"])

2번문제 ( 약간 창발적 문제 ) cpp

2번 문제 치고 좀 어려운 느낌이였다. 솔직히 문제 구조가 좀 좋았던 것 같다. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    reverse(deliveries.begin(), deliveries.end());
    reverse(pickups.begin(), pickups.end());
    for (int i=0; i<n; i++) {
        int d = deliveries[i];
        int p = pickups[i];
        if (d || p) {
            int count = max(d,p)/cap + (max(d,p)%cap?1:0);
            answer += count*(n-i)*2;
            int dcount = d/cap + (d%cap?1:0);
            int pcount = p/cap + (p%cap?1:0);
            deliveries[i] = 0;
            pickups[i] = 0;

            int remained = (count - dcount)*cap + (d%cap?(cap-d%cap):0);
            int j = i;
            while( ++j < n && remained > 0) {
                int canDeliver = min(remained, deliveries[j]);
                if (canDeliver){
                    remained -= canDeliver;
                    deliveries[j] -= canDeliver;
                }
            }
            remained = (count - pcount)*cap + (p%cap?(cap-p%cap):0);
            j = i;
            while( ++j < n && remained > 0) {
                int canPickup = min(remained, pickups[j]);
                if (canPickup){
                    remained -= canPickup;
                    pickups[j] -= canPickup;
                }
            }
        }
        // for (int i=0; i<n; i++) {
        //     cout << deliveries[i]<< " " ;
        // }
        // cout <<"\n";
        // for (int i=0; i<n; i++) {
        //     cout << pickups[i] << " ";
        // }
        // cout <<"\n^^" << answer << "\n";
    }
    return answer;
}

int main(){
    // vector<int> input = {1,0,3,1,2};
    // vector<int> pickups = {0,3,0,4,0};
    vector<int> input = {1,0,2,0,1,0,2};
    vector<int> pickups = {0,2,0,1,0,2,0};

    // cout<< solution(4, 5, input, pickups);
    cout<< solution(2, 7, input, pickups);
}

3번문제 할인율 ( 탐색 문제 ) js

할인율이 지문에 숨겨져있어서 좀 헤맸다. 사실 지문에 숨겨져있지 않고 1~40%에서 선택하는 구조였다면 문제 구조상 각 제한시간 10초안에 풀수 있었을까? 생각이 든다.

그리고 문제에서 "10000원을 넘어가야" 라고 지문에 적혀있는데 이게 초과 개념이라 payment > userThresHold 라 작성했는데 "이상이면" (>=) 이라는 뜻이였다. 크흠 

let insdAnswer = 0;
let buyAnswer = 0;
let stateAnswer;
const visited = new Set()

function goFind(users, emoticons, state, rates) {
    const d = state.map(String).join(',')
    if(visited.has(d)) return;
    visited.add(d);

    let insdCount = 0;
    let buyPayment = 0;
    for (user of users){
        let payment = 0;
        const userLikeRate = user[0];
        const userThreadsHold = user[1];
        for (let i =0; i<emoticons.length; i++){
            if (userLikeRate > state[i] ) continue;
            const bill = emoticons[i]*(100-state[i])/100
            payment += bill;
        }
        if (payment >= userThreadsHold) {
            insdCount++;
        } 
        else buyPayment += payment;
    }

    if (insdCount > insdAnswer) {
        insdAnswer = insdCount; 
        buyAnswer = buyPayment
        stateAnswer = state;
    }

    if (insdCount == insdAnswer && buyPayment >= buyAnswer) {
        buyAnswer = buyPayment;
        stateAnswer = state;
    }

    for (let i=0; i<state.length; i++) {
        const curRate = state[i]; 
        const index = rates.findIndex(rate => rate==curRate);
        if (index == rates.length-1) continue;
        let nextIndex = index+1;
        while(true){
            if (nextIndex == rates.length ) break;
            const nextRate = rates[nextIndex];
            const nextState = [...state];
            nextState[i] = nextRate;
            goFind(users, emoticons, nextState, rates);
            if (++nextIndex == rates.length) {
                break;
            }
        }
    }
}

function solution(users, emoticons) {
  var answer = [];
  rates = [...new Set(users.map(a=>a[0]).sort((a, b)=> b-a))]
  // 모든 사용자가 구매했을 때의 가격 
  const initialState = Array(emoticons.length).fill(10)
  goFind(users, emoticons, initialState, [10, 20, 30, 40]);
  console.log(insdAnswer, buyAnswer, stateAnswer);
  return [insdAnswer, buyAnswer];
}

solution( 
    [ [40, 10000], [25, 10000], ], 
    [7000, 9000] 
);

solution( 
    [ [40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900] ], 
    [1300, 1500, 1600, 4900]
);


function test(users, emoticons, state) {
    // const users = [[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]] 
    // const state = [5, 11, 40 , 40];
    // const emoticons= [1300, 1500, 1600, 4900];

    let insdCount =0;
    let buyPayment = 0;
    for (user of users){
        let payment = 0;
        const userLikeRate = user[0];
        const userThreadsHold = user[1];

        for (let i =0; i<emoticons.length; i++){
            if (userLikeRate > state[i] ) continue;
            const bill = emoticons[i]*(100-state[i])/100
            payment += bill;
        }

        console.log(user, userLikeRate, userThreadsHold, payment)
        if (payment >= userThreadsHold) {
            insdCount++;
        } 
        else buyPayment += payment;
    }
    console.log(insdCount, buyPayment);
}

test(
    [ [40, 10000], [25, 10000], ], 
    [7000, 9000] ,
    [25, 40]
);


test( 
    [ [40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900] ], 
    [1300, 1500, 1600, 4900],
    [40 , 40, 20, 40]
);

4번문제  ( 이진트리 constructive algorithm 느낌) cpp

쉽다면 쉬운 문제, 2번문제보다 쉬운 느낌이였다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

string buildTree(string str) {
    int height = 1;
    int len = str.size();
    while(true) {
        int elem = pow(2, height)-1;
        if (elem >= len) break;
        height++;
    }
    string suffix;
    int elem = pow(2, height) -1;
    for (int i=0; i<elem-len; i++) {
        suffix += "0";
    }
    string result = suffix + str;
    return result;
}

bool validCheck(string str, int f, int t) {
    int mid = (f+t)/2;
    // cout << f << " , " << t << ", " << "idx: " << mid <<"\n";
    if (f == t) return true;
    if (str[mid]=='1') {
        bool result = validCheck(str, f, mid-1);
        result &= validCheck(str, mid+1, t);
        return result;
    }

    bool result = true;
    for (int i=f; i<=t; i++) {
        result &= str[i]=='0';
    }
    return result;
}

vector<int> solution(vector<long long> numbers) {
    vector<int> answer;
    for (long long number: numbers){
        long long origin = number;
        string str;
        while(number){
            str += ('0' + (number%2));
            number /= 2;
        }
        reverse(str.begin(), str.end());
        cout << str <<"\n";
        string treeStr = buildTree(str);
        int len = treeStr.size();
        // cout << len <<"\n";
        int _answer = validCheck(treeStr, 0, len-1);
        answer.push_back(_answer);
    }

    // for (bool ans: answer) {
    //     cout << ans << " ";
    // }
    // cout <<"\n-------\n";
    return answer;
}

int main(){
    solution({7, 5});
    solution({63, 111, 95});
    solution({2, 4});
    solution({1024});
    solution({0b11111111111111111111111111111111111111111111111111111111111111});
}

 

이후로 6번 문제를 바로 풀었는데 1시간 50분 잡고 못풀었다. 5번 문제가 유니온 파인드 문제여서 잡을걸 그랬다. 지문이 길어서 허허, 바로 패스했었지만 .. 

P.S: 일단 근데 난 탈락일듯? 400점 을 못 넘겼다.