Codetesing의 코딩공부

2018 카카오 블라인드 공채 1차 코테 문제

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

코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스 (programmers.co.kr)

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

중복을 허용한 문제였기 때문에 set을 사용할 수 는 없었고 내가 만들어 처리해야했다.

먼저 각각의 string을 나눠 set을 만든다. 다만 대소문자 구분이 없이 같다 처리하기 때문에 하나로 바꿔서 set을 만든다.

그 후, 각각의 set을 sort하여 교집합을 구하면 된다. 문제에서 묻는것은 J이기 때문에, 교집합의 갯수와 합집합의 갯수만 구하면 된다.

하지만 전체 갯수  = 합집합의 갯수 + 교집합의 갯수이므로 둘중 하나만 구하면 된다.

교집합의 갯수가 구하기 쉽기때문에 교집합의 개수만 구하면 정답이 나온다.

교집합의 개수를 구하는것은 , FIFO형태를 이용하였으며, 각 집합의 제일 앞을 비교하며 갯수를 구할 것이다.

각 집합의 제일 앞을 비교하였을때, 같으면 교집합의 갯수를 늘려주고, 다르다면 내림차순으로 sort 하였기 때문에 크기가 작은것을 빼준다.

지금보니 투포인터라는 방식과 유사한것같다.

그렇게 교집합의 수를 구한 후, 합집합의 수는 집합의 수를 더하여 교집합의 수를 뺴면 된다.

물론 집합이 비었을때의 처리도 해주어야한다.

#define MUL 65536

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

using namespace std;

int solution(string str1, string str2) {
    int answer = 0;

    vector<string> set1;
    vector<string> set2;

    for (int i = 0; i < str1.size() - 1; i++)
        if (isalpha(str1[i]))
        {
            if (isalpha(str1[i + 1]))
            {
                string temp = "";
                temp += (char)tolower(str1[i]);
                temp += (char)tolower(str1[i + 1]);
                set1.push_back(temp);
            }
            else
                i++;
        }

    for (int i = 0; i < str2.size() - 1; i++)
        if (isalpha(str2[i]))
        {
            if (isalpha(str2[i + 1]))
            {
                string temp = "";
                temp += (char)tolower(str2[i]);
                temp += (char)tolower(str2[i + 1]);
                set2.push_back(temp);
            }
            else
                i++;
        }

    sort(set1.begin(), set1.end());
    sort(set2.begin(), set2.end());

    int common = 0;
    int uncomm = set1.size() + set2.size();
    double J;

    if (uncomm == 0)
        J = 1;

    else
    {
        while (!set1.empty() && !set2.empty())
        {
            if (set1[0] == set2[0])
            {
                common++;
                set1.erase(set1.begin());
                set2.erase(set2.begin());
            }
            else if (set1[0] > set2[0])
                set2.erase(set2.begin());
            else
                set1.erase(set1.begin());
        }

        uncomm -= common;
        J = (double)common / uncomm;
    }

    answer = J * MUL;

    return answer;
}

2018 카카오 블라인드 공채 1차 코테 문제

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

코딩테스트 연습 - [1차] 셔틀버스 | 프로그래머스 (programmers.co.kr)

5번 문제였으며 1시간 30분 정도 소요되었다.

가장 시간이 많이 걸렸던 문제였으며, 많이 꼬였던 문제다.

제일 처음, 시간을 빨리온 순서대로 sort해야하는데 C++의 문자열 sorting에 대해 정확히 알지 못해 꼬일수도 있다 판단하여 int로 변경한 후, 내림차순으로 sorting 해 주었다.

그 후, 탈 수 있는 인원과 막차 시간을 계산하여 반복문 없이 조건과 값을 이용해 풀 수 있을 줄 알았다.

여기에 갖다버린 시간이 족히 30분은 될것이다.

하지만 그렇게 풀려니 계산도 복잡하고 되는지 안되는지도 모르겠어서 그냥 simulation형태로 반복해주며 진행해주었다.

FIFO형태로 풀었으며, 마지막 버스 전까지는 모든 버스에 탈 수 있는 최대한의 인원을 태우고, 마지막 버스에서는  자신이 타야하기 때문에 한자리를 남기고 태워야 한다.

그렇기 때문에 마지막 사람을 태우고 남은 인원중에 제일 앞에 있는 사람보다 빨리 오면 된다. (제일 앞에 있는 사람 시간 - 1)

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

using namespace std;

string solution(int n, int t, int m, vector<string> timetable) {
    string answer = "";
    vector<int> time;

    for (int i = 0; i < timetable.size(); i++)
    {
        string H = timetable[i].substr(0, 2);
        string M = timetable[i].substr(3, 2);

        time.push_back(stoi(H) * 60 + stoi(M));
    }

    sort(time.begin(), time.end());

    int last = 9 * 60 + t * (n - 1);
    int limit_num = m * n;

    int cnt = 0;
    int flag = 0;
    int temp;
    
    int start = 9 * 60;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (time.empty())
                break;

            if (time[0] <= start)
                time.erase(time.begin());
            else
                break;
        }
        start += t;
    }

    for (int j = 0; j < m - 1; j++)
    {
        if (time.empty())
            break;

        if (time[0] <= start)
            time.erase(time.begin());
        else
            break;
    }

    if (time.empty())
        temp = last;
    else
    {
        if (time[0] <= last)
            temp = time[0] - 1;
        else
            temp = last;
    }

    int H = temp / 60;
    int M = temp % 60;

    if (H < 10)
        answer += "0";
    answer += to_string(H);
    answer += ":";
    if (M < 10)
        answer += "0";
    answer += to_string(M);

    return answer;
}

2018 카카오 블라인드 공채 1차 코테 문제

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

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스 (programmers.co.kr)

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

내리는 문자열 처리가 쉽지 않을꺼라 생각하여 오른쪽으로 90도 회전하고 삭제되면 왼쪽으로 미는형태로 풀기로 하였다.

그렇게 되면 삭제되는 블록은 string의 erase로 쉽게 처리할 수 있을꺼라 생각했다.

블록이 중복으로 제거되는것을 허용하였기 때문에 바로 지우지 않고 visited로 체크만 해주었다.

모든 블럭을 확인한 후, visited가 true인것의 수를 세고, true면 블록을 지워주었다.

다시보면 매개변수로 m, n이 들어오는데 일반적이지 않고 90도 회전하라고 힌트를 주는것 같다.

#include <string>
#include <vector>

using namespace std;

bool deleted[30][30] = { false };
int row, col;
vector<string> board;

int FIND_DELETE_NUM()
{
    bool visited[30][30] = { false };
    int num = 0;

    for (int i = 0; i < row - 1; i++)
    {
        if (board[i].size() < 2 || board[i + 1].size() < 2)
            continue;

        for (int j = 0; j < board[i].size() - 1; j++)
        {
            char temp = board[i][j];

            if ((temp == board[i + 1][j]) && (temp == board[i][j + 1]) && (temp == board[i + 1][j + 1]))
            {
                visited[i][j] = true;
                visited[i + 1][j] = true;
                visited[i][j + 1] = true;
                visited[i + 1][j + 1] = true;
            }
        }
    }

    for (int i = 0; i < row; i++)
    {
        int ind = 0;
        for (int j = 0; j < board.size(); j++)
        {
            if (visited[i][j])
            {
                board[i].erase(board[i].begin() + j - ind);
                num++;
                ind++;
            }
        }
    }

    return num;
}

int solution(int m, int n, vector<string> s) {
    int answer = 0;

    for (int i = 0; i < n; i++)
    {
        string temp = "";
        for (int j = m - 1; j >= 0; j--)
            temp += s[j][i];
        board.push_back(temp);
    }
    row = n; col = m;
    while (1)
    {
        int deleted_num = FIND_DELETE_NUM();
        if (deleted_num == 0)
            break;
        else
            answer += deleted_num;
    }
    return answer;
}

2018 카카오 블라인드 공채 1차 코테 문제

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

코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr)

3번 문제 였으며 약 30분 정도 소요되었음.

LRU방식이었으므로 cache에 저장된 문자열만 저장할 것이 아니라, 

각 cache가 언제 사용 되었는지도 저장한다.

cities의 순서대로 진행하면 되는데, cities는 대소문자 구분이 없었으므로 하나로 변환해준다.

그 후, cache에 없으면 사용한지 제일 오래된 (visited_num의 값이 제일 작은) cache를 제거하고 변경하고,

있으면 visited_num의 수를 최신으로 변경해준다.

처음 제출할 때, cachesize가 0일때 고려하지 않아 실패 처리 됐었다.

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

using namespace std;

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;

    if (cacheSize == 0)
        return 5 * cities.size();

    vector<string> cache(cacheSize);
    vector<int> visited_num(cacheSize, -1);
    vector<string>::iterator it;

    for (int i = 0; i < cities.size(); i++)
    {
        for (int j = 0; j < cities[i].size(); j++)
            if (isupper(cities[i][j]))
                cities[i][j] = tolower(cities[i][j]);

        it = find(cache.begin(), cache.end(), cities[i]);
        if (it == cache.end())
        {
            int min_ind = min_element(visited_num.begin(), visited_num.end()) - visited_num.begin();
            cache[min_ind] = cities[i];
            visited_num[min_ind] = i;
            answer += 5;
        }
        else
        {
            visited_num[it - cache.begin()] = i;
            answer += 1;
        }
    }

    return answer;
}

2018 카카오 블라인드 공채 1차 코테 문제

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

코딩테스트 연습 - [1차] 비밀지도 | 프로그래머스 (programmers.co.kr)

2번 문제로 약 5분 정도 소요되었다.

bit연산을 이용하여 풀었으며 어려울건 없었다.

bit연산을 사용하지 않으면 푸는데 오래 걸릴 문제.

#include <string>
#include <vector>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
    vector<string> answer;

    for (int i = 0; i < n; i++)
    {
        string in = "";
        int temp = arr1[i] | arr2[i];

        for (int j = 0; j < n; j++)
        {
            if (temp & (1 << j))
                in = '#' + in;
            else
                in = ' ' + in;
        }
        answer.push_back(in);
    }
    
    return answer;
}