Codetesing의 코딩공부

크게 어렵진 않았다.

소수 판별은 하던대로 했고, DFS로 숫자를 만들어주었다.

다만 중복제거를 위해 vector를 사용해 모두 저장한 후 중복삭제했다.

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

using namespace std;

vector<int> prime;
string n;
bool visited[10] = { false };

bool IS_PRIME(int n)
{
    if (n < 2)
        return false;

    if (n == 2 || n == 3)
        return true;

    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
            return false;

    return true;
}

void DFS(int ind, int cnt, string cur)
{
    visited[ind] = true;

    if (IS_PRIME(stoi(cur)))
        prime.push_back(stoi(cur));

    for (int i = 0; i < n.size(); i++)
        if (!visited[i])
            DFS(i, cnt + 1, cur + n[i]);
    visited[ind] = false;
}

int solution(string numbers) {
    int answer = 0;
    n = numbers;

    for (int i = 0; i < numbers.size(); i++)
        DFS(i, 1, to_string(numbers[i] - '0'));

    sort(prime.begin(), prime.end());
    prime.erase(unique(prime.begin(), prime.end()), prime.end());

    answer = prime.size();

    return answer;
}

크게 어렵진 않았다.

sort의 cmp를 +로 구현하면 된다.

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

using namespace std;

bool cmp(string a, string b)
{
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    vector<string> temp;

    for (int i = 0; i < numbers.size(); i++)
        temp.push_back(to_string(numbers[i]));

    string answer = "";

    sort(temp.begin(), temp.end(), cmp);

    if (temp[0] == "0")
        return "0";

    for (int i = 0; i < temp.size(); i++) 
        answer += temp[i];

    return answer;
}

priority_queue 와 queue 모두 써서 푸는 문제였다.

q로 대기열을 계속 바꾸고 pq로 출력 할 지 안할지 확인한다.

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0, count = 0;
    queue<pair<int, int>> q;
    priority_queue <int> pq;

    for (int i = 0; i < priorities.size(); i++) {
        q.push(make_pair(i, priorities[i]));
        pq.push(priorities[i]);
    }

    while (!q.empty()) {
        int index = q.front().first;
        int value = q.front().second;
        q.pop();

        if (pq.top() == value) {

            pq.pop();

            count++;

            if (index == location) {
                answer = count;
                break;
            }
        }
        else
            q.push(make_pair(index, value));
    }
    return answer;
}

쉬운 문제였다.

phone_number의 len 을 hash function으로 보고 풀었다.

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

using namespace std;

vector<vector<string>> hash_table(21);

bool IS_HASH_TABLE(string str)
{
    for (int i = 1; i < str.size(); i++)
        for (int j = 0; j < hash_table[i].size(); j++)
            for (int k = 0; k < hash_table[i][j].size(); k++)
            {
                if (str[k] != hash_table[i][j][k])
                    break;
                else
                    if (k == hash_table[i][j].size() - 1)
                        return true;
            }

    return false;
}

bool solution(vector<string> phone_book) {

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

    hash_table[phone_book[0].size()].push_back(phone_book[0]);

    for (int i = 1; i < phone_book.size(); i++)
    {
        if (IS_HASH_TABLE(phone_book[i]))
            return false;
        else
            hash_table[phone_book[i].size()].push_back(phone_book[i]);
    }
    return true;
}

처음에 문제가 이해가 안갔는데 결론은 방향도 맞아야 사이클로 치는것이다.

그후엔 평범한 DFS문제였다.

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

using namespace std;

vector<string> map;
bool visited[501][501][4] = { false };

int NEXT_ROW[] = { 0, 1, 0, -1 };
int NEXT_COL[] = { -1, 0, 1, 0 };
int N, M;

int CHANGE(char A, int dir)
{
    if (A == 'R')
    {
        if (dir == 0) return 1;
        if (dir == 1) return 2;
        if (dir == 2) return 3;
        if (dir == 3) return 0;
    }
    else
    {
        if (dir == 0) return 3;
        if (dir == 1) return 0;
        if (dir == 2) return 1;
        if (dir == 3) return 2;
    }
}

int DFS(int row, int col, int dir, int len)
{
    if (visited[row][col][dir])
        return len;

    visited[row][col][dir] = true;

    int next_row = row;
    int next_col = col;
    int next_dir = dir;

    if (map[row][col] != 'S')
        next_dir = CHANGE(map[row][col], dir);

    next_row += NEXT_ROW[next_dir];
    next_col += NEXT_COL[next_dir];

    if (next_row == -1)
        next_row = N - 1;
    if (next_row == N)
        next_row = 0;
    if (next_col == -1)
        next_col = M - 1;
    if (next_col == M)
        next_col = 0;

    return DFS(next_row, next_col, next_dir, len + 1);
}

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

    map = grid;
    N = grid.size();
    M = grid[0].size();

    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            for (int k = 0; k < 4; k++)
            {
                int len = DFS(i, j, k, 0);
                if (len != 0)
                    answer.push_back(len);
            }

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

    return answer;
}