3223. Minimum Length of String After Operations

문제 링크


내 코드

그냥 3개 이상일 때 2개 깎기.

14ms, 32.04MB

class Solution {
public:
    int minimumLength(string s) {
        vector counting(26, 0);
        for(char c : s) {
            counting[c - 'a']++;
            if(counting[c - 'a'] >= 3) counting[c - 'a'] -= 2;
        }

        int answer{};
        answer = accumulate(begin(counting), end(counting), 0);

        return answer;
    }
};

Solution

Approach 1: Using Hash Map

  • 40ms, 32.63MB
  • Complexity
    • Let nn be the size of the string s, and let k be the size of the character set.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1) or O(k)O(1) \ or \ O(k)
class Solution {
public:
    int minimumLength(string s) {
        // Step 1: Count the frequency of each character in the string
        unordered_map<char, int> charFrequencyMap;
        for (char currentChar : s) {
            charFrequencyMap[currentChar]++;
        }

        // Step 2: Calculate the number of characters to delete
        int deleteCount = 0;
        for (auto& pair : charFrequencyMap) {
            int frequency = pair.second;
            if (frequency % 2 == 1) {
                // If frequency is odd, delete all except one
                deleteCount += frequency - 1;
            } else {
                // If frequency is even, delete all except two
                deleteCount += frequency - 2;
            }
        }

        // Step 3: Return the minimum length after deletions
        return s.length() - deleteCount;
    }
};

GPT (o3-mini-high)

이 코드는 문자열 s에서 특정 삭제 연산을 수행한 후 도달할 수 있는 “최소 길이”를 계산합니다.
코드의 로직은 각 문자의 등장 횟수를 이용해, 각 문자마다 남겨야 하는 최소 개수를 결정하고, 그 결과 전체 남은 문자 수(최소 길이)를 구하는 방식입니다.

문제의 조건(정확한 문제 설명은 주어지지 않았지만)을 유추해보면,

  • 홀수 횟수로 등장하는 문자는 삭제 연산을 통해 결국 1개만 남길 수 있고,
  • 짝수 횟수로 등장하는 문자는 2개만 남길 수 있다는 규칙에 기반한 것으로 보입니다.

아래에서 단계별로 코드를 설명하겠습니다.

1. 각 문자의 등장 횟수 세기

unordered_map<char, int> charFrequencyMap;
for (char currentChar : s) {
    charFrequencyMap[currentChar]++;
}
  • 역할:
    문자열 s의 각 문자에 대해 등장 횟수를 세어, charFrequencyMap에 저장합니다.
  • 예시:
    s = "aaabbc"인 경우,
    • 'a'의 빈도: 3
    • 'b'의 빈도: 2
    • 'c'의 빈도: 1

2. 삭제해야 할 문자 개수 계산

int deleteCount = 0;
for (auto& pair : charFrequencyMap) {
    int frequency = pair.second;
    if (frequency % 2 == 1) {
        // If frequency is odd, delete all except one
        deleteCount += frequency - 1;
    } else {
        // If frequency is even, delete all except two
        deleteCount += frequency - 2;
    }
}
  • 핵심 아이디어:
    각 문자에 대해 남겨야 하는 최소 개수를 결정합니다.
    • 홀수 빈도:
      • 예를 들어 빈도가 3인 문자라면, 3‑1 = 2개를 삭제하여 1개만 남김.
    • 짝수 빈도:
      • 예를 들어 빈도가 4인 문자라면, 4‑2 = 2개를 삭제하여 2개만 남김.
  • 결과:
    전체 삭제 횟수 deleteCount는 s에서 삭제되어 없어지는 문자들의 총 개수가 됩니다.

3. 최소 길이 계산

return s.length() - deleteCount;
  • 계산 방식:
    원래 문자열 길이에서 삭제한 문자 수를 빼면, 최종적으로 남는 문자열의 최소 길이가 됩니다.
  • 예시:
    s = "aaabbc"인 경우
    • 'a': 빈도 3 → 남겨야 하는 개수 1 → 삭제: 3‑1 = 2
    • 'b': 빈도 2 → 남겨야 하는 개수 2 → 삭제: 2‑2 = 0
    • 'c': 빈도 1 → 남겨야 하는 개수 1 → 삭제: 1‑1 = 0
      총 삭제: 2개
      최종 길이: 6 - 2 = 4

최종 요약

  • 목적:
    문자열 s에서 각 문자의 빈도를 기준으로,

    • 홀수 빈도인 경우 1개만 남기고,
    • 짝수 빈도인 경우 2개만 남긴다고 가정할 때,
      삭제할 문자 개수를 누적하여 최종적으로 남을 수 있는 최소 길이를 반환합니다.

  • 주의점:
    이 풀이 방식은 문제에서 “각 문자는 홀수이면 1개, 짝수이면 2개만 남길 수 있다”는 조건이나 규칙이 주어졌음을 전제로 합니다.
    문제의 정확한 삭제 연산이나 조건에 따라 풀이가 달라질 수 있으므로,
    실제 문제 조건과 맞는지 확인하는 것이 중요합니다.

  • 시간 복잡도:
    문자열을 한 번 순회하여 빈도를 세고, 각 문자(최대 26종류)를 다시 순회하므로 O(n) (n = s의 길이)입니다.

이와 같이, 코드는 문자열 s에서 각 문자별로 최종적으로 남겨야 하는 최소 개수를 계산하여, 삭제 후 남은 최소 길이를 구하는 방법을 구현한 것입니다.


Approach 2: Using Frequency Array

  • 11ms, 31.96MB
  • Complexity
    • Let nn be the size of the string s, and let k be the size of the character set.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1) or O(k)O(1) \ or \ O(k)
class Solution {
public:
    int minimumLength(string s) {
        // Step 1: Initialize a frequency array to count occurrences of each
        // character
        vector<int> charFrequency(26, 0);
        int totalLength = 0;

        // Step 2: Count the frequency of each character in the string
        for (char currentChar : s) {
            charFrequency[currentChar - 'a']++;
        }

        // Step 3: Calculate the total length after deletions count
        for (int frequency : charFrequency) {
            if (frequency == 0) continue;  // Skip characters that don't appear
            if (frequency % 2 == 0) {
                totalLength += 2;  // If frequency is even, add 2
            } else {
                totalLength += 1;  // If frequency is odd, add 1
            }
        }

        // Step 4: Return the minimum length after deletions count
        return totalLength;
    }
};

GPT (o3-mini-high)

이 코드는 문자열 s에 대해, 주어진 삭제 규칙에 따라 최적의 삭제를 진행한 후 남을 수 있는 최소 길이를 계산하는 솔루션입니다.
여기서 삭제 규칙(문제 조건)은 각 문자별로 다음과 같이 남길 수 있는 최소 개수가 정해진다고 가정합니다:

  • 한 문자가 홀수 번 등장하면, 모든 짝을 삭제한 후 1개가 남을 수 있다.
  • 한 문자가 짝수 번 등장하면, 모든 짝을 삭제해도 2개를 남기는 것이 최선이다.

즉, 문자열에 등장하는 각 문자에 대해 최종적으로 남을 수 있는 최소 개수는

  • 홀수 빈도 → 1개
  • 짝수 빈도 → 2개

최종 최소 길이는 s에 등장하는 서로 다른 문자들에 대해 위의 최소 개수를 모두 합한 값이 됩니다.

아래에서 코드를 단계별로 자세히 설명합니다.

Step 1. 문자 빈도수 배열 초기화

vector<int> charFrequency(26, 0);
int totalLength = 0;
  • charFrequency:
    알파벳 소문자 'a'부터 'z'까지의 등장 횟수를 저장하는 크기 26의 배열입니다.
    모든 원소를 0으로 초기화합니다.
  • totalLength:
    삭제 작업 후 남게 될 문자열의 최소 길이를 누적할 변수입니다.

Step 2. 문자열 내 각 문자의 빈도수 계산

for (char currentChar : s) {
    charFrequency[currentChar - 'a']++;
}
  • 문자열 s의 모든 문자에 대해 해당 문자의 아스키 코드 차이를 이용하여
    charFrequency 배열의 올바른 인덱스를 찾아 등장 횟수를 증가시킵니다.
  • 예를 들어, s = "aabccc"인 경우:
    • 'a' → 2회
    • 'b' → 1회
    • 'c' → 3회

Step 3. 각 문자별로 삭제 후 남을 개수 합산

for (int frequency : charFrequency) {
    if (frequency == 0) continue;  // 문자열에 등장하지 않는 문자는 건너뜀
    if (frequency % 2 == 0) {
        totalLength += 2;  // 짝수 빈도인 경우, 최종적으로 2개 남김
    } else {
        totalLength += 1;  // 홀수 빈도인 경우, 최종적으로 1개 남김
    }
}
  • 빈도수가 0인 문자는 s에 등장하지 않으므로 무시합니다.
  • 각 문자가 등장하는 횟수에 따라
    • 짝수이면 최적의 삭제를 통해 2개를 남기는 것이 최선이라고 가정하여 2를 더합니다.
    • 홀수이면 1개만 남길 수 있으므로 1을 더합니다.
  • 예를 들어, s = "aabccc"인 경우
    • 'a': 2회 → 짝수 → 남길 수 있는 최소 개수는 2
    • 'b': 1회 → 홀수 → 남길 수 있는 최소 개수는 1
    • 'c': 3회 → 홀수 → 남길 수 있는 최소 개수는 1
      최종 totalLength = 2 + 1 + 1 = 4

Step 4. 최종 결과 반환

return totalLength;
  • 위에서 계산한 totalLength가 삭제 작업을 최적으로 수행했을 때 남을 수 있는 문자열의 최소 길이가 됩니다.

결론

이 솔루션은 문자열 s의 각 문자가 등장하는 횟수를 이용하여,

  • 홀수번 등장하는 문자는 1개,
  • 짝수번 등장하는 문자는 2개가 남는다고 가정하고
    각 문자별 최소 남김 개수를 합산하여 최종 길이를 계산합니다.

시간 복잡도는 문자열을 한 번 순회하는 O(n)와 26글자(상수)의 반복으로 구성되어 O(n)이며,
공간 복잡도는 알파벳 26개에 대한 배열을 사용하므로 O(1)입니다.

주의:
이 코드의 삭제 규칙(짝수번이면 2개, 홀수번이면 1개 남음)이 문제의 조건과 정확히 일치해야 하며,
실제 문제에서 요구하는 삭제 연산의 규칙에 따라 이 풀이가 유효한지 확인해야 합니다.


Approach 3: Using Bitwise

  • 8ms, 32.05MB
  • Complexity
    • Let nn be the size of the string s.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    int minimumLength(string s) {
        int present = 0;
        int parity = 0;
        int placevalue;

        // Iterate through the string and update the present and parity bitmasks
        for (int k = 0; k < s.size(); k++) {
            // Calculate the bit position for the character
            placevalue = 1 << (s[k] - 'a');
            // Set the corresponding bit in the present bitmask
            present |= placevalue;
            // Toggle the corresponding bit in the parity bitmask
            parity ^= placevalue;
        }

        int totalLength = 0;

        // Process the present bitmask and check the parity bitmask to calculate
        // the minimum length
        while (present) {
            // Clear the least significant bit in present
            placevalue = present & (present - 1);
            // If the corresponding parity bit is set, it indicates an odd
            // occurrence, so add 1
            totalLength += 2 - ((parity & (present - placevalue)) != 0);
            present = placevalue;
        }

        return totalLength;
    }
};

GPT

이 코드는 문자열 s에서 등장하는 각 알파벳에 대해,

  • 짝수 번 등장하는 문자는 최종적으로 2개씩
  • 홀수 번 등장하는 문자는 최종적으로 1개만 남길 수 있다고 가정하여,
    삭제 후 남을 수 있는 최소 길이를 비트마스크(bitmask)를 이용해 계산하는 방식입니다.

아래 단계별로 코드를 자세히 설명합니다.

1. 비트마스크 변수 초기화

int present = 0;
int parity = 0;
int placevalue;

  • present:
    문자열 s에서 등장한 알파벳들을 기록하기 위한 비트마스크입니다.
    예를 들어, 'a'가 한 번 이상 등장하면 비트 0이 1로 설정됩니다.

  • parity:
    각 알파벳의 등장 횟수의 홀짝(parity)을 기록하는 비트마스크입니다.
    문자열을 순회하면서 해당 문자가 등장할 때마다 XOR 연산을 사용하여 비트를 토글합니다.
    최종적으로, 특정 알파벳에 대응하는 비트가 1이면 홀수번 등장, 0이면 짝수번 등장한 것을 의미합니다.

  • placevalue:
    각 문자에 해당하는 비트의 위치(값)를 저장하는 변수입니다.

2. 문자열 순회 – 비트마스크 업데이트

for (int k = 0; k < s.size(); k++) {
    // 현재 문자에 해당하는 비트 위치 계산 (예: 'a' → 1<<0, 'b' → 1<<1, …)
    placevalue = 1 << (s[k] - 'a');
    // present 비트마스크에 현재 문자를 표시 (이미 등장했더라도 그대로 유지)
    present |= placevalue;
    // parity 비트마스크에서는 현재 문자의 비트를 토글 (짝수번이면 0, 홀수번이면 1)
    parity ^= placevalue;
}

  • present |= placevalue;
    현재 문자가 등장했음을 기록합니다.
    이미 기록된 경우에도 변화가 없으므로, 이 비트마스크에는 s에 등장한 모든 서로 다른 문자의 비트가 1로 설정됩니다.

  • parity ^= placevalue;
    XOR 연산으로 각 문자의 등장 횟수를 홀짝 토글합니다.
    예를 들어, 'a'가 3번 등장했다면, 처음에는 0에서 1로, 두 번째 등장에서 1→0, 세 번째 등장에서 0→1로 토글되어 최종적으로 1(홀수)을 나타냅니다.

3. 남은 문자들을 기반으로 최소 길이 계산

int totalLength = 0;

// present에 기록된 각 문자(비트)가 남아있는 동안 반복
while (present) {
    // present의 가장 낮은 자리의 1을 제거하기 전의 값과 제거 후의 값의 차이를 이용
    // present & (present - 1)는 present에서 가장 낮은 1비트를 제거한 결과입니다.
    placevalue = present & (present - 1);
    
    // present - placevalue는 방금 제거한, 가장 낮은 set bit의 값을 구하는 효과와 같습니다.
    // 만약 (parity & (present - placevalue)) != 0이면 해당 문자의 등장 횟수가 홀수라는 의미입니다.
    //  - 홀수이면 최종적으로 1개만 남기므로 (2 - 1) = 1을 더합니다.
    //  - 짝수이면 최종적으로 2개 남기므로 (2 - 0) = 2를 더합니다.
    totalLength += 2 - ((parity & (present - placevalue)) != 0);
    
    // present를 갱신하여 이미 처리한 비트를 제거합니다.
    present = placevalue;
}

  • 비트 연산 트릭:

    • present & (present - 1)는 현재 present에서 가장 낮은 set bit(즉, 가장 낮은 자리의 1)를 0으로 만드는 연산입니다.
    • 따라서, present - (present & (present - 1))는 현재 present에서 제거된 그 한 비트의 값(예: 1<<i)을 나타냅니다.

  • (parity & (present - placevalue)) != 0:

    • 이 표현식은 현재 처리 중인 문자(해당 비트)가 홀수 번 등장했는지 검사합니다.
    • 만약 홀수이면, 결과는 true(1)이고, 그렇지 않으면 false(0)가 되어,
      totalLength에 2 - 1 = 1 또는 2 - 0 = 2가 더해집니다.

즉, 모든 등장한 문자에 대해:

  • 홀수번 등장 → 결과에 1을 더함
  • 짝수번 등장 → 결과에 2를 더함

이 계산은 앞의 풀이에서 빈도 배열을 사용하여

“빈도수가 홀수이면 1, 짝수이면 2”
를 더하는 것과 동일한 결과를 얻습니다.

4. 최종 결과 반환

return totalLength;
  • 계산된 totalLength는
    주어진 규칙(각 문자가 홀수이면 1개, 짝수이면 2개 남김)에 따라 삭제 후 남을 수 있는 최소 길이를 의미합니다.

요약

  1. 문자열 순회 및 비트마스크 구성:

    • present: 등장한 문자를 기록
    • parity: 각 문자의 등장 횟수 홀짝을 토글하여 기록

  2. 각 문자별 최소 남길 개수 계산:

    • 비트마스크 present를 반복적으로 순회하면서,
    • 해당 문자의 홀짝 정보(parity)에 따라 최종 남겨야 할 개수를 결정 (홀수이면 1, 짝수이면 2)

  3. 최종 최소 길이 반환.

이와 같이, 비트 연산을 활용하여 각 문자별 등장 횟수의 홀짝 정보를 빠르게 집계하고, 이를 바탕으로 최소 길이를 계산하는 알고리즘입니다.