문제 링크

내 코드

문제 내에 힌트 참고.

• If the s.length < k we cannot construct k strings from s and answer is false.
• If the number of characters that have odd counts is > k then the minimum number of palindrome strings we can construct is > k and answer is false.
• Otherwise you can construct exactly k palindrome strings and answer is true (why ?).

5ms, 15MB

/* 
2 2 2 2 1
1 3 1 1 1 1
1 1 1 1

// 홀수 그룹의 수.
qlkzenwmmnpkopu, 15
aaa, 2
cr, 7
jsautfnlcmwqpzycehdulmdencthhlzsnijd, 35
*/
class Solution {
public:
    bool canConstruct(string s, int k) {
        vector dat(26, 0);
        for(char c : s) {
            dat[c - 'a']++;
        }

        int oddCnt{};
        int groupCnt{};
        for(int d : dat) {
            if(!d) continue; // 0개.

            // 5 -> 2
            // 4 -> 4
            if(d & 1) {
                ++oddCnt;
                groupCnt += d - 1;
            }
            else groupCnt += d;
        }
        
        if(oddCnt > k) return false; // oddCnt 개수는 넘어야 함.
        else if(k <= oddCnt + groupCnt) return true; // 가능 최대 개수
        return false;
    }
};

Solution

Editorial이 다른 문제인데 올라온 것 같음.

GPT (o3-mini-high)

문자열 s의 문자들을 재배열하여 k개의 팰린드롬 문자열을 만들 수 있는지 여부를 판단하는 문제입니다.
핵심 아이디어는 다음과 같습니다.

• 팰린드롬의 성질:
  팰린드롬은 양쪽 대칭이므로, 보통 모든 문자는 짝수 번 등장해야 합니다. 단, 중앙에 단 하나의 홀수 개 문자는 허용됩니다.

• 문제 접근:
  s의 모든 문자를 사용하여 k개의 팰린드롬을 만들 때, 각 팰린드롬은 중앙에 최대 한 개의 홀수 개수를 가진 문자를 가질 수 있습니다.
  따라서 s에 있는 홀수 빈도의 문자의 개수를 oddCount라고 할 때, 각 홀수 빈도의 문자는 서로 다른 팰린드롬의 중앙에 배치되어야 합니다.
  즉, 팰린드롬을 만들기 위해서는 k가 최소한 oddCount 이상이어야 합니다.

• 추가 조건:

  • 만약 k가 s의 길이보다 크다면, 빈 문자열이 허용되지 않으므로 만들 수 없습니다.
    (즉, 각 팰린드롬은 최소 한 글자 이상이어야 하므로 k ≤ s.size() 여야 합니다.)

따라서 조건은 두 가지입니다.

1. $k \le s.\text{size()}$
2. $\text{oddCount} \le k$

---

코드 구현 (C++)

0ms, 15.03MB

class Solution {
public:
    bool canConstruct(string s, int k) {
        // k개의 팰린드롬을 만드려면, s의 길이가 k 이상이어야 합니다.
        if (k > s.size()) {
            return false;
        }
        
        // 각 문자의 빈도수를 저장할 벡터 (알파벳 소문자 26개)
        vector<int> freq(26, 0);
        for (char c : s) {
            freq[c - 'a']++;
        }
        
        // 홀수 빈도의 문자가 몇 개인지 계산
        int oddCount = 0;
        for (int count : freq) {
            if (count % 2 == 1) {
                oddCount++;
            }
        }
        
        // 각 팰린드롬은 최대 한 개의 홀수 빈도 문자를 가질 수 있으므로,
        // 홀수 빈도 문자의 개수가 k보다 많으면 k개의 팰린드롬을 만들 수 없습니다.
        return oddCount <= k;
    }
};

---

코드 설명

1. k와 s의 길이 비교

   • if (k > s.size()) return false;
     문자열 s의 길이보다 더 많은 팰린드롬을 만들 수는 없습니다.

2. 문자 빈도수 계산

   • vector<int> freq(26, 0);
     문자열 s의 각 문자가 몇 번 등장하는지 세기 위해 길이 26의 벡터를 사용합니다.
   • 각 문자에 대해 해당 인덱스의 값을 증가시킵니다.

3. 홀수 빈도의 문자 개수 세기

   • 모든 문자의 빈도수를 순회하면서 홀수인 경우 oddCount를 증가시킵니다.

4. 조건 검사 후 반환

   • 각 팰린드롬은 중앙에 최대 한 개의 홀수 개 문자를 가질 수 있으므로, oddCount가 k 이하이면 모든 홀수 빈도 문자를 서로 다른 팰린드롬에 배치할 수 있습니다.
   • 따라서 return oddCount <= k;를 통해 조건에 맞으면 true, 그렇지 않으면 false를 반환합니다.

이와 같이 구현하면, 문자열 s의 모든 문자들을 사용하여 정확히 k개의 팰린드롬 문자열을 구성할 수 있는지를 효율적으로 판단할 수 있습니다.