[코테연습] 1405. Longest Happy String

- 그리디 / 힙 / 우선순위 큐 문제

 

https://leetcode.com/problems/longest-happy-string/description/?envType=daily-question&envId=2024-10-16

 

- 문제분석

 

 

• 주어진 a, b, c는 각각 문자 'a', 'b', 'c'가 등장할 수 있는 최대 횟수를 나타냅니다.
• 목표는 이 조건을 만족하는 가장 긴 문자열을 만드는 것이며, **"aaa", "bbb", "ccc"**와 같은 연속된 문자가 나오지 않도록 해야 합니다.

- 문제풀이

 

 

• 최대 빈도를 우선 사용하되, 연속되지 않게 만들기:
  • 문자열을 만들 때, 가장 많이 남아 있는 문자부터 선택하는 것이 중요합니다.
  • 하지만 동일한 문자를 연속해서 2번까지만 사용할 수 있으므로, 그 이상 반복하려면 다른 문자를 끼워 넣어야 합니다.
• 우선순위 큐 또는 정렬을 활용:
  • 각 문자의 개수를 관리하면서, 가장 남은 개수가 많은 문자를 우선적으로 선택하는 것이 효율적입니다.
  • 예를 들어, 'a'의 개수가 가장 많다면 'a'를 최대 2번 넣고, 다음으로 남은 문자를 선택해 이어가는 식으로 문제를 해결할 수 있습니다.
• 예시:
  • a = 1, b = 1, c = 7인 경우:
    • 먼저 'c'가 많으므로, 가능한 최대 연속 횟수인 "cc"를 먼저 선택합니다.
    • 이후에는 'a' 또는 'b'를 끼워넣어 "ccbcc" 또는 "ccabc" 같은 패턴을 만듭니다.
  • a = 2, b = 2, c = 1인 경우:
    • "aabbc"와 같은 패턴을 만들 수 있습니다. 이 경우 각 문자를 가능한 균등하게 분배하는 것이 중요합니다.
• 종료 조건:
  • 더 이상 유효한 선택이 없거나, 사용할 문자가 없을 때 문자열 생성을 종료합니다.

 

 

> java

 

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2[1], o1[1]));

        if (a > 0) pq.offer(new int[]{'a', a});
        if (b > 0) pq.offer(new int[]{'b', b});
        if (c > 0) pq.offer(new int[]{'c', c});

        StringBuilder sb = new StringBuilder();

        while (!pq.isEmpty()) {

            int[] first = pq.poll();

            if ( sb.length() >= 2 &&
                sb.charAt(sb.length()-2) == first[0] &&
                sb.charAt(sb.length()-1) == first[0] ) {
                
                if ( pq.isEmpty() ) {
                    break;
                }

                int[] second = pq.poll();
                sb.append((char)second[0]);
                if (--second[1] > 0) {
                    pq.offer(second);
                }
                pq.offer(first);
            } else {
                sb.append((char)first[0]);
                if (--first[1] > 0) {
                    pq.offer(first);
                }

            }

        }

        return sb.toString();
    }
}

 

 

> python

 

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        pq = []

        if a > 0 : heapq.heappush(pq, (-a, 'a'))
        if b > 0 : heapq.heappush(pq, (-b, 'b'))
        if c > 0 : heapq.heappush(pq, (-c, 'c'))

        result = []

        while pq :
            first_count, first_char = heapq.heappop(pq)
            first_count = -first_count

            if len(result) >= 2 and result[-1] == first_char and result[-2] == first_char :
                if not pq : break

                second_count, second_char = heapq.heappop(pq)
                second_count = -second_count
                
                result.append(second_char)
                second_count -= 1

                if second_count > 0 : heapq.heappush(pq, (-second_count, second_char))

                heapq.heappush(pq, (-first_count, first_char))

            else :

                result.append(first_char)
                first_count -= 1

                if first_count > 0 : heapq.heappush(pq, (-first_count, first_char))

        return ''.join(result)