1. Buddy Strings (친밀한 문자열)

두 개의 문자열 s와 goal이 주어졌을 때, s의 두 문자를 단 한 번 교체하여 goal과 동일하게 만들 수 있는지 확인하는 문제입니다.

풀이 전략:

1. 두 문자열의 길이가 다르면 절대 같아질 수 없으므로 false를 반환합니다.
2. 두 문자열이 이미 같다면, 문자열 내에 중복된 문자가 하나라도 있어야 교체 후에도 동일함을 유지할 수 있습니다.
3. 두 문자열이 다르다면, 서로 다른 위치가 정확히 두 곳이어야 하며, 그 두 위치의 문자를 서로 바꿨을 때 일치해야 합니다.

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if (s.length() != goal.length()) return false;

        if (s == goal) {
            vector<int> alphabet(26, 0);
            for (char c : s) {
                if (++alphabet[c - 'a'] > 1) return true;
            }
            return false;
        }

        vector<int> diff;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] != goal[i]) diff.push_back(i);
        }

        return diff.size() == 2 && 
               s[diff[0]] == goal[diff[1]] && 
               s[diff[1]] == goal[diff[0]];
    }
};

2. Score of Parentheses (괄호의 점수)

균형 잡힌 괄호 문자열의 점수를 다음 규칙에 따라 계산하는 문제입니다: ()는 1점, AB는 A + B점, (A)는 2 * A점입니다.

풀이 전략:

괄호의 깊이(depth)를 추적하며 문제를 해결할 수 있습니다. (를 만날 때마다 깊이를 1 증가시키고, )를 만나면 깊이를 1 감소시킵니다. () 형태의 가장 안쪽 괄호를 만났을 때, 현재 깊이에 해당하는 가중치(2^(depth))를 결과에 더해주는 방식으로 최적화가 가능합니다.

class Solution {
public:
    int scoreOfParentheses(string s) {
        int total = 0, level = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                level++;
            } else {
                level--;
                if (s[i - 1] == '(') {
                    total += (1 << level);
                }
            }
        }
        return total;
    }
};

3. Mirror Reflection (거울 반사)

정사각형 방의 구석에서 발사된 레이저가 반대편 벽에 도달할 때까지 반사됩니다. 어느 수신기에 가장 먼저 도달하는지 찾는 문제입니다.

풀이 전략:

방을 계속해서 위로 쌓아 올린다고 가정하면, 레이저가 수신기에 도달하는 지점은 k * p = m * q가 되는 지점입니다. 여기서 k는 방을 쌓은 횟수 관련 변수이고, m은 수평 이동 횟수 관련 변수입니다. p와 q의 최소공배수를 활용하여 문제를 단순화할 수 있습니다.

class Solution {
public:
    int mirrorReflection(int p, int q) {
        // p와 q를 공약수가 없을 때까지 2로 나눔
        while (p % 2 == 0 && q % 2 == 0) {
            p /= 2;
            q /= 2;
        }
        // p가 짝수면 2번 수신기
        if (p % 2 == 0) return 2;
        // q가 짝수면 0번 수신기, 둘 다 홀수면 1번 수신기
        return (q % 2 == 0) ? 0 : 1;
    }
};

4. Minimum Cost to Hire K Workers (K명의 노동자 고용 최소 비용)

노동자의 업무 질(quality)과 최저 임금(wage)이 주어질 때, 두 가지 규칙(비례 임금 지급, 최저 임금 보장)을 만족하며 K명을 고용하는 최소 비용을 구하는 문제입니다.

풀이 전략:

1. 각 노동자의 wage / quality 비율을 계산하고 이 비율을 기준으로 오름차순 정렬합니다.
2. 정렬된 리스트를 순회하면서 특정 노동자의 비율을 '기준 비율'로 설정합니다.
3. 이때까지 확인한 노동자 중 quality가 낮은 순서대로 K명을 선택해야 비용이 최소가 됩니다. 이를 위해 최대 힙(Max Heap)을 사용하여 가장 큰 quality를 가진 노동자를 제거하며 관리합니다.

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        vector<pair<double, int>> workers;
        for (int i = 0; i < n; ++i) {
            workers.push_back({(double)wage[i] / quality[i], quality[i]});
        }
        sort(workers.begin(), workers.end());

        priority_queue<int> max_q;
        int q_sum = 0;
        double min_cost = 1e18;

        for (auto& worker : workers) {
            double ratio = worker.first;
            q_sum += worker.second;
            max_q.push(worker.second);

            if (max_q.size() > k) {
                q_sum -= max_q.top();
                max_q.pop();
            }

            if (max_q.size() == k) {
                min_cost = min(min_cost, (double)q_sum * ratio);
            }
        }
        return min_cost;
    }
};