Codetesing의 코딩공부

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

2019 카카오 인턴 코테 문제

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

코딩테스트 연습 - 크레인 인형뽑기 게임 | 프로그래머스 (programmers.co.kr)

1번 문제였으며 쉬운문제였다. 약 20분정도 소요되었다.

moves의 순서대로 반복문을 돌리면 된다.

stack의 형태로 생각하여 구현하면 어렵지 않다.

뽑힌 인형과 뽑힐인형을 나눠 뽑힐인형을 뽑은 후, stack에 있는 뽑힌인형의 마지막을 확인한 후, 같다면 stack에서 pop하면 된다,

pop될때, 인형은 2개씩 사라지므로, 답을 2씩 증가시켜주면 된다.

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    vector<int> temp;
    for (int i = 0; i < moves.size(); i++)
    {
        int ind = moves[i] - 1;
        for(int j = 0; j < board.size(); j++)
            if (board[j][ind])
            {
                if (temp.empty())
                    temp.push_back(board[j][ind]);
                else
                {
                    if (temp[temp.size() - 1] == board[j][ind])
                    {
                        answer += 2;
                        temp.pop_back();
                    }
                    else
                        temp.push_back(board[j][ind]);
                }
                board[j][ind] = 0;
                break;
            }
    }

    return answer;
}