Codetesing의 코딩공부

그냥 막히는거 없이 구현했다.

별도의 알고리즘도 필요하지 않아 쉬운거같다.

#include <iostream>

#include <string>
#include <vector>

using namespace std;

string TO_BINARY(int n)
{
    string re = "";

    for (; n != 0; n /= 2)
    {
        if (n % 2 == 0)
            re = '0' + re;
        else
            re = '1' + re;
    }

    return re;
}

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

    while (1)
    {
        int cnt = 0;
        if (s == "1")
            break;

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

        answer[0]++;
        answer[1] += s.size() - cnt;

        s = TO_BINARY(cnt);
    }

    return answer;
}

완전탐색으로 풀려다가 규칙이 있는거 같아 확인해 보니 풀렸다.

경우의 수로 미리 설정해두고 풀었다.

#include <string>
#include <vector>

using namespace std;

int solution(string word) {
    int answer = word.length();
    int n[] = { 781, 156, 31, 6, 1 };
    string alpha = "AEIOU";
    
    for (int i = 0; i < word.length(); i++)
        answer += n[i] * alpha.find(word[i]);

    return answer;
}

크게 어렵진 않은 문제였다.

DFS로 계속 완전 탐색 하였다.

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

using namespace std;

vector<vector<int>> G(101, vector<int>());
bool visited[101] = { false };

void DFS(vector<int> execpt, int ind, int cnt)
{
    visited[ind] = true;

    for (int i = 0; i < G[ind].size(); i++)
    {
        int next = G[ind][i];

        if (visited[next]) continue;
        if (ind == execpt[0] && next == execpt[1]) continue;
        if (ind == execpt[1] && next == execpt[0]) continue;

        DFS(execpt, next, cnt + 1);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = n;

    for (int i = 0; i < wires.size(); i++)
    {
        G[wires[i][0]].push_back(wires[i][1]);
        G[wires[i][1]].push_back(wires[i][0]);
    }

    for (int i = 0; i < wires.size(); i++)
    {
        DFS(wires[i], 1, 1);
        
        int group_num = 0;

        for (int j = 1; j <= n; j++)
            if (visited[j])
                group_num++;
                
        int dif = n - group_num;
        answer = min(answer, abs(group_num - dif));

        for (int j = 1; j <= n; j++)
            visited[j] = false;
        group_num = 0;
    }

    return answer;
}

크게 어려운건 없었다.

투포인터 방식을 이용해서 풀었다.

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;

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

    int start = 0, end = people.size() - 1;

    while (start <= end)
    {
        if (people[start] + people[end] <= limit)
        {
            start++;
            end--;
            answer++;
        }
        else
        {
            end--;
            answer++;
        }
    }

    return answer;
}

stack 으로 풀라 했지만 time의 차이가 없어 보이길래 그냥 반복문으로 풀었음.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;

    for (int i = 0; i < prices.size(); i++)
    {
        int time = 0;
        for (int j = i + 1; j < prices.size(); j++)
        {
            time++;
            if (prices[i] > prices[j])
                break;
        }
        answer.push_back(time);
    }

    return answer;
}