Codetesing의 코딩공부

2021 카카오 인턴 코테 문제

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

코딩테스트 연습 - 거리두기 확인하기 | 프로그래머스 (programmers.co.kr)

2번 문제 였으며, 30분 정도 소요되었다.

크게 어려운건 없었으나 처음에 BFS로 풀다가 DFS로 바꿔 풀었다.

무작정 2차원 배열을 확인할때 BFS로 푸는 습관은 버려야겠다.

전형적인 DFS문제 였으며 다만 2차원 배열에서의 DFS를 이용한 완전탐색 문제였다.

#include <string>
#include <vector>

using namespace std;

int N = 5;
vector<vector<string>> map;

int ROTATE_X[] = { -1, 0, 0, 1 };
int ROTATE_Y[] = { 0, -1, 1, 0 };

bool visited[5][5][5] = { false };

bool DFS(int ind, int row, int col, int cnt)
{
    visited[ind][row][col] = true;

    if (cnt != 0)
    {
        if (map[ind][row][col] == 'P')
            return false;
        if (cnt == 2)
            return true;
    }
    for (int i = 0; i < 4; i++)
    {
        int next_row = row + ROTATE_X[i];
        int next_col = col + ROTATE_Y[i];

        if (next_row < 0 || next_col < 0 || next_row >= N || next_col >= N || visited[ind][next_row][next_col])
            continue;

        if (!DFS(ind, next_row, next_col, cnt + 1))
            return false;
    }

    return true;
}

bool IS_OK(int ind)
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (map[ind][i][j] == 'X')
                visited[ind][i][j] = true;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (map[ind][i][j] == 'P')
            {
                if (!DFS(ind, i, j, 0))
                    return false;
            }
    return true;
}

vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    map = places;

    for (int i = 0; i < N; i++)
    {
        if (IS_OK(i))
            answer.push_back(1);
        else
            answer.push_back(0);
    }

    return answer;
}

2021 카카오 인턴 코테 문제

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

코딩테스트 연습 - 숫자 문자열과 영단어 | 프로그래머스 (programmers.co.kr)

1번 문제이며, 약 20분 소요되었다.

크게 어려운 것은 없으며 map을 이용하여 풀었다. 파이썬의 dict이 더 편할지 모르겠다.

다만 string 처리가 귀찮았다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(string s) {
    int answer = 0;
    string num = "";
    string temp = "";
    map<string, string> m;
    m["zero"] = "0";
    m["one"] = "1";
    m["two"] = "2";
    m["three"] = "3";
    m["four"] = "4";
    m["five"] = "5";
    m["six"] = "6";
    m["seven"] = "7";
    m["eight"] = "8";
    m["nine"] = "9";

    for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]))
            num += s[i];
        else
        {
            temp += s[i];
            if (m[temp]  != "")
            {
                num += m[temp];
                temp = "";
            }
        }
    }

    answer = stoi(num);

    return answer;
}

2020 카카오 인턴 코테 문제

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

코딩테스트 연습 - 경주로 건설 | 프로그래머스 (programmers.co.kr)

4번문제였으며, 남은 1시간 30분 모두 빡빡하게 썻다.

bfs로 풀었다. 다만 여기선 전의 방향이 추가로 필요하였다.

#include <iostream>

#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef struct pos {
    int x;
    int y;
    int cost;
    int dir;
}pos;

int ROTATE_X[] = { -1, 0, 1, 0 };
int ROTATE_Y[] = { 0, 1, 0, -1 };

int solution(vector<vector<int>> board) {
    int answer = 987654321;
    int N = board.size();
    queue<pos> q;
    vector<vector<vector<int>>> map(4, vector<vector<int>>(N, vector<int>(N, 987654321)));
    q.push({ 0, 0, 0, 1 });
    q.push({ 0, 0, 0, 2 });
    map[1][0][0] = 0;
    map[2][0][0] = 0;
    pos cur;
    

    while (!q.empty())
    {
        cur = q.front();
        q.pop();

        if (cur.x == N - 1 && cur.y == N - 1)
        {
            answer = min(answer, cur.cost);
            continue;
        }

        for (int i = 0; i < 4; i++)
        {
            int next_row = cur.x + ROTATE_Y[i];
            int next_col = cur.y + ROTATE_X[i];

            if (next_row < 0 || next_col < 0 || next_row >= N || next_col >= N || board[next_row][next_col] == 1)
                continue;

            int cur_cost;
            if (cur.dir == i)
                cur_cost = cur.cost + 100;
            else
                cur_cost = cur.cost + 600;

            if (map[i][next_row][next_col] >= cur_cost)
            {
                map[i][next_row][next_col] = cur_cost;
                q.push({ next_row, next_col, cur_cost, i });
            }

        }
    }
    return answer;
}

2020 카카오 인턴 코테 문제

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

코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 (programmers.co.kr)

3번 문제였으며 효율성과 정확도가 나뉜 문제이다. 약 두시간정도 걸렸다.

투포인터 문제였으며, 일반적인 투포인터 문제이다.

투포인터로 푸는건 알았으나 바로 접근방법이 떠오르지 않아 시간이 많이 걸렸다.

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

using namespace std;

vector<int> solution(vector<string> gems) {
    vector<int> answer(2, 0);
    map<string, int> gem;

    for (auto& i : gems)
        gem[i] = 0;

    int start = 0, end = 0;
    int gem_size = gem.size();
    int gem_cnt = 0;
    int min_len = 100001;
    while (1)
    {
        if (gem_cnt == gem_size)
        {
            if (end - start < min_len)
            {
                answer[0] = start + 1;
                answer[1] = end;
                min_len = end - start;
            }

            if (gem[gems[start]] <= 1)
                gem_cnt--;
            gem[gems[start]]--;
            start++;
        }
        else
        {
            if (end == gems.size())
                break;

            if (gem[gems[end]] == 0)
                gem_cnt++;
            gem[gems[end]]++;
            end++;
        }
    }

    return answer;
}

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;
}