Codetesing의 코딩공부

그리디라 쓰여있어서 쉬웠던 문제.

아니었으면 완전탐색으로 먼저 풀었을꺼같다.

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int ind = -1;

    for (int i = 0; i < number.size() - k; i++)
    {
        char max_n = ' ';
        for(int j = ind + 1; j <= k + i; j++)
            if (max_n < number[j])
            {
                ind = j;
                max_n = number[j];
            }
        answer += max_n;
    }

    return answer;
}

쉬웠다. 완전 탐색이라고 쓰여있지 않았어도 쉽게 풀었을꺼 같다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    int n = brown / 2;
    for (int i = 1; i <= n; i++)
    {
        int temp = n - i;
        if (i * (temp - 2) == yellow)
        {
            answer.push_back(temp);
            answer.push_back(i + 2);
            break;
        }
    }

    return answer;
}

문제 이해가 안가서 시간이 좀 걸렸다.

구현은 쉬웠던 문제.

#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b)
{
    return a > b;
}

int solution(vector<int> citations) {

    sort(citations.begin(), citations.end(), compare);

    for (int i = 0; i < citations.size(); i++)
        if (citations[i] <= i)
            return i;
}

쉬웠다. queue를 이용해서 그냥 구현해주면 되었다.

쉽게 시간을 1씩 늘려가면서 구현하면 되었다.

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

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int ind = 0;
    int sum = 0;
    queue<int> bridge;

    while (1)
    {
        if (ind == truck_weights.size())
            return answer + bridge_length;

        answer++;
        
        if (bridge.size() == bridge_length)
        {
            sum -= bridge.front();
            bridge.pop();
        }

        if (sum + truck_weights[ind] <= weight)
        {
            sum += truck_weights[ind];
            bridge.push(truck_weights[ind]);
            ind++;
        }
        else
            bridge.push(0);
    }
}

되게 쉬웠다.

장착하지 않음을 하나의 옵션으로 생각하여 풀면 된다.

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, int> hash;

    for (int i = 0; i < clothes.size(); i++)
        hash[clothes[i][1]]++;

    for (map<string, int>::iterator it = hash.begin(); it != hash.end(); it++)
        answer *= (it->second) + 1;

    return --answer;
}