1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake that is full of water, there will be a flood. Your goal is to avoid floods in any lake.

Given an integer array rains where:

rains[i] > 0 means there will be rains over the rains[i] lake.
rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.
Return an array ans where:

ans.length == rains.length
ans[i] == -1 if rains[i] > 0.
ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.
If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes.

당신의 나라에는 무한히 많은 호수가 있습니다. 처음에는 모든 호수가 비어 있지만, n번째 호수 위로 비가 내리면 그 호수는 물로 가득 찹니다. 이미 물로 가득 찬 호수에 비가 내리면 홍수가 발생합니다. 당신의 목표는 어떤 호수에서도 홍수가 발생하지 않도록 하는 것입니다.
정수 배열 rains가 주어졌을 때:

rains[i] > 0은 rains[i]번 호수에 비가 내린다는 것을 의미합니다.
rains[i] == 0은 그날 비가 내리지 않아 당신이 원하는 하나의 호수를 선택해 물을 말릴 수 있다는 것을 의미합니다.

다음 조건을 만족하는 배열 ans를 반환하세요:

ans.length == rains.length
rains[i] > 0일 경우 ans[i] == -1
rains[i] == 0일 경우 ans[i]는 그날 당신이 물을 말릴 호수의 번호입니다. 단, 말릴 수 있는 물로 가득 찬 호수가 없을 경우에는 반드시 1번 호수를 말립니다.

유효한 답이 여러 개일 경우 그중 하나를 반환하면 됩니다. 홍수를 피할 수 없는 경우 빈 배열을 반환하세요.만약 당신이 물로 가득 찬 호수를 말리기로 선택하면 그 호수는 비게 되지만, 이미 비어 있는 호수를 말리기로 선택하면 아무 변화도 일어나지 않습니다.

---

예시

[1,2,0,0,2,1]

[-1,-1,2,1,-1,-1]

• 2번째 index의 0에서 2번 호수를 말림
• 3번째 index의 0에서 1번 호수를 말림

---

제한

• $1 <= rains.length <= 10^5$
• $0 <= rains[i] <= 10^9$

---

풀이

해당 문제를 풀기 위해선 반드시 필요한 자료형이 3가지가 있다.

1. 0의 위치를 항상 정렬한 상태로 저장해두는 SortedList
2. 비가 내렸던 호수 번호를 key, 내린 시간을 value로 가지는 dictionary
3. 정답을 저장하는 배열 ans ( 미리 -1로 채워둔 rains와 동일한 사이즈의 배열 )

어떻게 접근하는가?

1. 먼저 rains를 순회하되 값이 0이면 넘어가고 0이 아닐때에만 2번부터 수행한다.
2. 만약 0이 아닌값이 들어오면 2가지 경우의 수로 넘어간다.

• A: 2번 dict에 호수 키값이 없을 경우
  • 그냥 dict에 호수번호, 내린 시간으로 추가
• B: 2번 dict에 호수 키값이 있을 경우
  • 이렇게 되면 기존에 있었던 value와 현재 내린 비의 index의 사이에 0이 있어서 미리 물이 말랐어야 한다.
  • 자료구조의 1번 SortedList에서 이진탐색을 통해 찾고, 있으면 제거 없으면 빈 배열을 리턴한다.

최종적으로 1번 SortedList에 남은 값들에 대해 ans에 1로 채우면 된다.

from sortedcontainers import SortedList

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        N = len(rains)  # 입력 배열 rains의 길이
        # 0이 나타나는 인덱스를 정렬된 상태로 저장 (SortedList로 0의 위치를 추적)
        zeroes = SortedList([i for i, v in enumerate(rains) if v == 0])
        # 호수 번호를 키로, 비가 내린 시간을 값으로 저장하는 딕셔너리
        placement = dict()
        # 정답을 저장할 배열, 초기값은 -1로 채움 (rains와 동일한 길이)
        ans = [-1] * N

        # rains 배열을 순회하며 각 인덱스와 값을 처리
        for i, v in enumerate(rains):
            if v != 0:  # 비가 내린 경우 (호수 번호가 0이 아닌 경우)
                if v not in placement:  # 해당 호수에 처음으로 비가 내린 경우
                    # 호수 번호와 비가 내린 시간을 딕셔너리에 저장
                    placement[v] = i
                else:  # 해당 호수에 이미 비가 내린 적이 있는 경우
                    # 이전 비가 내린 시간과 현재 시간을 가져옴
                    left_value = placement[v]
                    right_value = i

                    # SortedList에서 이전 비와 현재 비 사이의 0 인덱스를 찾기 위해 이진 탐색
                    left = bisect_left(zeroes, left_value)  # 이전 비 이후 첫 0의 위치
                    right = bisect_left(zeroes, right_value)  # 현재 비 이전 마지막 0의 위치

                    # 두 위치 사이의 0의 개수 계산
                    count = right - left

                    if count == 0:  # 0이 없으면 물을 말릴 기회가 없으므로 불가능
                        return []

                    # 사용 가능한 첫 번째 0의 인덱스를 선택
                    target = zeroes[left]
                    # 해당 0의 인덱스를 SortedList에서 제거
                    zeroes.remove(target)
                    # 정답 배열에서 해당 인덱스에 호수 번호를 기록 (물을 말린 호수)
                    ans[target] = v
                    # 딕셔너리의 호수 시간을 현재 시간으로 갱신
                    placement[v] = i

        # 남은 0의 인덱스에 대해 임의로 1을 채움 (아무 호수나 말릴 수 있음)
        for z in zeroes:
            ans[z] = 1

        # 최종 정답 배열 반환
        return ans