Codetesing의 코딩공부

2020 카카오 인턴 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

코딩테스트 연습 - 수식 최대화 | 프로그래머스 (programmers.co.kr)

2번 문제였으며 약 1시간 정도 소요되었다.

dfs를 써서 각 우선순위의 연산자 순서대로 배열에 넣으며 계산한다.

어렵지는 않았으나 바로 생각이 안났었다.

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

using namespace std;

vector<long long> num;
vector<char> operand_pred;
map<int, char> temp;
bool visited[3] = { false };
string operand_list = "";
int cnt = 0;
long long ans = 0;

long long calculate(long long a, long long b, char op)
{
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
}

long long calculate_all()
{
    vector<long long> cal = num;
    string op_list = operand_list;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < op_list.size(); j++)
        {
            if (op_list[j] == operand_pred[i])
            {
                long long res = calculate(cal[j], cal[j + 1], op_list[j]);
                cal.erase(cal.begin() + j);
                cal[j] = res;
                op_list.erase(op_list.begin() + j);
                j--;
            }
        }
    }

    return abs(cal[0]);
}

void DFS(int ind)
{
    if (ind == 3)
    {
        long long res = calculate_all();
        ans = max(res, ans);
        return;
    }

    for (int i = 0; i < 3; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            operand_pred.push_back(temp[i]);
            DFS(ind + 1);
            operand_pred.pop_back();
            visited[i] = false;
        }
    }
}

long long solution(string expression) {
    long long answer = 0;
    temp[0] = '+';
    temp[1] = '-';
    temp[2] = '*';

    string n = "";
    for (int i = 0; i < expression.size(); i++)
    {
        if (!isdigit(expression[i]))
        {
            num.push_back(stoll(n));
            n = "";
            operand_list += expression[i];
        }
        else
            n += expression[i];
    }
    num.push_back(stoll(n));

    DFS(0);

    answer = ans;
    return answer;
}

2020 카카오 인턴 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

코딩테스트 연습 - 키패드 누르기 | 프로그래머스 (programmers.co.kr)

1번문제였으며 쉬웠다. 약 30분 소요되었다.

그냥 빡구현 문제이며, 다른 1번보단 시간이 오래 걸렸다.

조건만 잘 설정한다면 크게 어려울것은 없다.

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int nums[4][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {-1, 0, -1} };

string solution(vector<int> numbers, string hand) {
    string answer = "";

    int left_row = 3, left_col = 0;
    int right_row = 3, right_col = 2;

    for (int i = 0; i < numbers.size(); i++)
    {
        if (numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7)
        {
            left_row = numbers[i] / 3;
            left_col = 0;
            answer += "L";
        }
        else if (numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9)
        {
            right_row = (numbers[i] / 3) - 1;
            right_col = 2;
            answer += "R";
        }
        else
            for (int m = 0; m < 4; m++)
                if (nums[m][1] == numbers[i])
                {
                    int left = abs(left_row - m) + abs(left_col - 1);
                    int right = abs(right_row - m) + abs(right_col - 1);

                    if (left > right)
                    {
                        right_row = m;
                        right_col = 1;
                        answer += "R";
                    }
                    else if (left < right)
                    {
                        left_row = m;
                        left_col = 1;
                        answer += "L";
                    }
                    else
                    {
                        if (hand == "right")
                        {
                            right_row = m;
                            right_col = 1;
                            answer += "R";
                        }
                        else
                        {
                            left_row = m;
                            left_col = 1;
                            answer += "L";
                        }
                    }
                    break;
                }
    }

    return answer;
}

2019 카카오 인턴코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

코딩테스트 연습 - 호텔 방 배정 | 프로그래머스 (programmers.co.kr)

4번 문제였으며  사실 여기 까지 풀 시간이 있을지 몰랐다.

생각보다 빠르게 풀려 4번을 풀 수 있는 기회가 생겼으며 남은 시간을 모두 여기에 썻다.

이문제는 정확도 테스트와 효율성 테스트가 나뉘어져 있었으며, 정확도 테스트밖에 통과하지 못했다.

알고리즘이 바로 기억안나고 최적화를 할 시간이 부족했다.

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

using namespace std;

long long FIND_EMPTY_NUM(vector<long long> num, long long n)
{
    while (1)
    {
        n++;
        if (find(num.begin(), num.end(), n) == num.end())
            return n;
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    vector<long long> parent(room_number.size(), 0);

    for (int i = 0; i < room_number.size(); i++)
    {
        vector<long long>::iterator it = find(answer.begin(), answer.end(), room_number[i]);
        if (it == answer.end())
            answer.push_back(room_number[i]);

        else
            answer.push_back(FIND_EMPTY_NUM(answer, room_number[i]));
    }

    return answer;
}

2019 카카오 인턴 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

코딩테스트 연습 - 불량 사용자 | 프로그래머스 (programmers.co.kr)

3번 문제이며, 정확도 테스트만 있어 생각보단 할만했다.

약 2시간정도 걸렸으며, 더 쉽게 풀 수 있는 방법이 있을꺼라 생각한다.

본인은 DFS를 이용하여 풀었으며, 단순히 풀다가 전체 중복처리에서 시간이 오래 걸렸었다.

#include <iostream>

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

using namespace std;

vector<string> user;
vector<string> ban;
vector<vector<string>> banned_list;
vector<string> temp;
int user_size, ban_size;
int ans = 0;
bool visited[8] = { false };

bool CAN_BAN(string a, string b)
{
    if (a.size() != b.size())
        return false;

    for (int i = 0; i < a.size(); i++)
        if (b[i] != '*' && a[i] != b[i])
            return false;

    return true;
}

bool IS_SAME()
{
    if (banned_list.size() == 0)
        return true;

    for (int i = 0; i < banned_list.size(); i++)
        for (int j = 0; j < temp.size(); j++)
        {
            if (find(banned_list[i].begin(), banned_list[i].end(), temp[j]) == banned_list[i].end())
                break;

            if (j == temp.size() - 1)
                return false;
        }
    return true;
}

void DFS(int user_ind, int banned_ind)
{
    if (banned_ind == ban_size - 1)
    {
        temp.push_back(user[user_ind]);
        
        if (IS_SAME())
            banned_list.push_back(temp);

        temp.pop_back();
        return;
    }

    visited[user_ind] = true;
    temp.push_back(user[user_ind]);
    banned_ind++;

    for (int i = 0; i < user_size; i++)
        if (i != user_ind && !visited[i])
            if (CAN_BAN(user[i], ban[banned_ind]))
                DFS(i, banned_ind);

    visited[user_ind] = false;
    temp.pop_back();
}

int solution(vector<string> user_id, vector<string> banned_id) {

    int answer = 0;
    user = user_id;
    ban = banned_id;
    user_size = user_id.size();
    ban_size = banned_id.size();

    for (int i = 0; i < user_size; i++)
        if (CAN_BAN(user_id[i], banned_id[0]))
            DFS(i, 0);

    answer = banned_list.size();

    return answer;
}

int main()
{
    vector<string> a = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> b = { "fr*d*", "*rodo", "******", "******" };

    solution(a, b);
}

2019 카카오 인턴 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

코딩테스트 연습 - 튜플 | 프로그래머스 (programmers.co.kr)

2단계치곤 쉬운문제였다. 약 30분정도 소요되었다.

문제의 답은 다음과 같이 구하면 된다.

원소 갯수가 1개짜리면 set에서 1번째, 2개짜리중 전체집합에 없는것이 set에서 2번째, ..... 하면 된다.

말로만봐선 이해하기 힘든데, 예시로 {a}, {b, a}, {c, b, a} 가 주어진다고 한다.

갯수가 1개짜리인 집합은 {a}  이고 이것이 전체 set에서 첫번째이므로 현재 전체 set은 {a} 이다. 

다음으로 2개짜리인 집합은 {b, a} 이며, 전체 집합에 없는것은 b이다.  따라서 전체집합은 {a, b} 가 된다.

마지막으로 3개짜리인 집합은 {c, b, a}이며, 전체집합에 없는것은 c이다. 따라서 전체집합은 {a, b, c}가 된다.

따라서 우리가 할 일은, string을 갯수에 따라 집합을 나눠 parsing하는 것이 다라고  볼 수 있다.

parsing은 { 이 들어온다면 } 이 나올때 까지 동일한 집합이며, 처음과 끝의 { } 를 빼고 생각한다면 쉽다.

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

using namespace std;

vector<int> solution(string s) {
    vector<int> answer;

    int cnt = 0;
    for (int i = 1; i < s.size() - 1; i++)
        if (s[i] == '{')
            cnt++;

    vector<vector<int>> set(cnt + 1);

    for (int i = 1; i < s.size() - 1; i++)
    {
        if (s[i] == '{')
        {
            i++;
            string num = "";
            vector<int> temp;
            while (i < s.size())
            {
                num += s[i];
                i++;
                if (s[i] == ',')
                {
                    temp.push_back(stoi(num));
                    num = "";
                    i++;
                }
                else if (s[i] == '}')
                {
                    temp.push_back(stoi(num));
                    break;
                }
            }
            
            set[temp.size()] = temp;
        }
    }

    for(int i = 1; i <= cnt; i++)
        for(int j = 0; j < set[i].size(); j++)
            if (find(answer.begin(), answer.end(), set[i][j]) == answer.end())
            {
                answer.push_back(set[i][j]);
                break;
            }

    return answer;
}