1405. Longest Happy String

https://leetcode.com/problems/shopping-offers/

Shopping Offers - LeetCode

a, b, c의 갯수가 주어지고

aaa, bbb, ccc와 같이 연속된 3개의 문자가 나오지 않는 선에서 가장 긴 스트링을 리턴하는 문제

 

한 번 재귀로 접근해보았는데... 계속 예외케이스가 발생하고 결국 중단.

재귀로 푼 다음 메모이제이션으로 최적화가 가능할 것 같았는데...

 

ccaccbcc 예시에서 막힘. 코드가 계속 복잡해지고 시간은 시간대로 잡아먹고, 아이디어는 잘 떠오르지 않아서 솔루션을 참고함.

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        
        memo = dict()
        
        return_longer = lambda a, b: a if len(a) > len(b) else b
        
        def dfs(an, bn, cn, last):
            key = tuple([an, bn, cn, last])
            if key in memo:
                return memo[key]
            
            ret = ""
            
            if (not last or last[-1] != "a") and an >= 2:
                ret = return_longer(ret, dfs(an-2, bn, cn, last+"aa"))
            if (not last or last[-1] != "b") and bn >= 2:
                ret = return_longer(ret, dfs(an, bn-2, cn, last+"bb"))
            if (not last or last[-1] != "c") and cn >= 2:
                ret = return_longer(ret, dfs(an, bn, cn-2, last+"cc"))
            
            if not ret:
                while an > 0:
                    inserted = False
                    if "bb" in last:
                        last = last.replace("bb", "bab", 1)
                        an -= 1
                        insrted = True
                    elif "cc" in last:
                        last = last.replace("cc", "cac", 1)
                        an -= 1
                        inserted = True
                    if not inserted:
                        break
                while bn > 0:
                    inserted = False
                    if "aa" in last:
                        last = last.replace("aa", "aba", 1)
                        bn -= 1
                        insrted = True
                    elif "cc" in last:
                        last = last.replace("cc", "cbc", 1)
                        bn -= 1
                        inserted = True
                    if not inserted:
                        break
                while cn > 0:
                    inserted = False
                    if "aa" in last:
                        last = last.replace("aa", "aca", 1)
                        cn -= 1
                        insrted = True
                    elif "bb" in last:
                        last = last.replace("bb", "bcb", 1)
                        cn -= 1
                        inserted = True
                    if not inserted:
                        break
                ret = last
                
            memo[key] = ret
            return ret
    
        return dfs(a, b, c, "")

 

20ms top solution

힙 큐를 이용해서 풀었다.

길이에 집중해서 긴 길이의 알파벳 부터 처리함.

heap에서 꺼낸 다음 바로 넣지 않고, 그 다음 것을 꺼내고 나서 넣어야한다.

그렇지 않으면, 갯수가 높은 놈이 계쏙 뽑힐 경우 aa aa aa 같은 상황이 일어날 수 있어서

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        res = ""
        heap = []
        if a:heapq.heappush(heap, (-a, "a"))
        if b:heapq.heappush(heap, (-b, "b"))
        if c:heapq.heappush(heap, (-c, "c"))
        
        total = a+b+c
        prev_c, prev_cnt = "", 0
        while heap:
            cnt, c = heapq.heappop(heap)
            cnt *= -1
            if prev_cnt > 0:
                heapq.heappush(heap, (-prev_cnt, prev_c))
            if cnt >= 2:
                add = 2 if cnt > total-cnt else 1
                res += c*add
                cnt -= add
                total -= add
            else:
                res += c
                cnt -= 1
                total -= 1
            prev_c, prev_cnt = c, cnt
        return res