[이취코] 유형별 알고리즘 - 구현(C++)

1. 럭키 스트레이트

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n = 7755;
    string s = to_string(n);
    int length = s.size() / 2;
    int pre = 0, post = 0;
    
    for (int i = 0; i < length; i++) {
        pre += s[i] - '0';
    }
    for (int i = length; i < s.size(); i++) {
        post += s[i] - '0';
    }

    if (pre != post) {
        cout << "READY";
    } else {
        cout << "LUCKY";
    }
    return 0;
}

 

2. 문자열 재정렬

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> num;
vector<char> ch;

int main() {
    string s;
    int n = 0;
    cin >> s;

    for (char & i : s) {
        if ((i >= 65 && i <= 90) || (i >= 97 && i <= 122)) {
            ch.push_back(i);
        } else
            num.push_back(i - '0');
    }

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

    for (auto &i: ch) {
        cout << i;
    }
    for (auto &i: num) {
        n += i;
    }
    cout << n;
    return 0;
}

 

3. 문자열 압축

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int solution(string s) {
    int answer = s.size();

    for (int i = 1; i <= s.size() / 2; i++) { //자르는 단위
        int cnt = 1;
        string stand = s.substr(0, i);
        string result;

        for (int j = i; j < s.size(); j += i) {
            string ver = s.substr(j, i);

            if (stand != ver) {
                if (cnt > 1) {
                    result += to_string(cnt);
                }
                result += stand;
                stand = ver;
                cnt = 1;
            } else {
                cnt++;
            }
        }

        if (cnt > 1)
            result += to_string(cnt);
        result += stand;

        if(answer > result.size()){
            answer = (int)result.size();
        }
    }
    return answer;
}

int main() {
    string s = "ababcdcdababcdcd";
    cout << solution(s);
    return 0;
}

 

치킨 배달

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 502
int n, m;
int map[MAX][MAX];
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
vector<pair<int, int>> choice;
int mi = 10000000;

int check(pair<int, int> h, vector<pair<int, int>> c) {  //house, choice -> choice 중 house와의 거리 제일 가까운 것 return
    int mimi = 10000000;
    for (auto &i: c) {
        int distance = abs(i.first - h.first) + abs(i.second - h.second);

        if (mimi > distance) {
            mimi = distance;
        }
    }
    return mimi;
}

void backtracking(int idx, int cnt) {
    if (cnt == m) { //고른 것 중 치킨 거리 최솟값들을 누적합
        int sum = 0;

        for (auto &i: house) {
            sum += check(i, choice);
        }

        if (mi > sum) {
            mi = sum;
        }

        return;
    }

    for (int i = idx; i < chicken.size(); i++) {
        choice.emplace_back(chicken[i].first, chicken[i].second);
        backtracking(idx + 1, cnt + 1);
        choice.pop_back();
    }
}

int main() { //n과 m으로 돌리며 cnt가 m이랑 같을 때가 여러번 있는데, 그때마다 min값 갱신
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];

            if (map[i][j] == 1) {
                house.emplace_back(i, j);
            } else if (map[i][j] == 2) {
                chicken.emplace_back(i, j);
            }
        }
    }

    backtracking(0, 0);
    cout << mi;
    return 0;
}