1. 문제 소개

1488. Avoid Flood in The City

2. 나의 풀이법

문제는 홍수가 나지 않도록 호수에 두 번 이상 비가 내리지 않도록 조절하는 것이다.
비가 두 번 오기 전, 어떤 순서로 호수에 고인 물을 빼내는 방법을 고민하는 것이 관건이다.

import heapq as hq

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        answer = [-1] * n
        full = set()
        heap = []
        next_rain = {}

        rain_days = {}
        for i, lake in enumerate(rains):
            if lake > 0:
                rain_days.setdefault(lake, []).append(i)

        for i, lake in enumerate(rains):
            if lake > 0:
                if lake in full:
                    return []
                full.add(lake)
                rain_days[lake].pop(0)
                if rain_days[lake]:
                    heapq.heappush(heap, (rain_days[lake][0], lake))
                answer[i] = -1
            else:
                if heap:
                    _, to_drain = heapq.heappop(heap)
                    full.remove(to_drain)
                    answer[i] = to_drain
                else:
                    answer[i] = 1

        return answer

3. 다른 풀이법

from sortedcontainers import SortedList

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        ans = [1] * len(rains)
        st = SortedList()
        mp = {}
        for i, rain in enumerate(rains):
            if rain == 0:
                st.add(i)
            else:
                ans[i] = -1
                if rain in mp:
                    it = st.bisect(mp[rain])
                    if it == len(st):
                        return []
                    ans[st[it]] = rain
                    st.discard(st[it])
                mp[rain] = i
        return ans

4. 결론

이번에는 나의 힘으로 푼 건이 아니라 정말 아쉽다.
다음에는 내 손으로 풀어보겠다.