[LeetCode - Online Assessment 기출] Stars and Bars* / 2055. Plates Between Candles

Stars and Bars*

• *과 |로 이루어진 문장이 주어진다. 
• 그리고 시작 인덱스와 종료 인덱스가 주어진다. 
• 시작 인덱스와 종료 인덱스는 최대 n개 까지 주어질 수 있다. 
• 한 쌍의 시작, 종료 인덱스 사이에 |(바)가 있고, 그 바들 사이에 *(별)이 몇개있는지를 각각 구하여라

예제

• s = '|**|*|*'
• startIndex = [1, 1]
• endIndex = [5, 6]
• answer = [2, 3]

제한사항

• 1 <= n <= 10^5
• 1 <= startIndex[i] <= endIndex[i] <=n
• s는 '*'과 '|'로만 구성되어있다.

 

비슷한 LeeCode 문제

2055. Plates Between Candles

 

Medium

There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti...righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

• For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

Return an integer array answer where answer[i] is the answer to the ith query.

 

Example 1:

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.

Example 2:

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.

 

Constraints:

• 3 <= s.length <= 105
• s consists of '*' and '|' characters.
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= lefti <= righti < s.length

---

문제 풀이

• 제한 사항에서 N이 최악의 경우 10^5 이다. 
• O(N^2) 인 브루트 포스로도 풀 수 있지만, 시간초과가 발생한다. 
• O(NlogN) 인 바이너리 서치나, O(N) 인 프리픽스 섬으로 문제를 풀 수 있다.

브루트 포스

• 쿼리에서 시작값과 끝값으로 문자열을 자른다. 
• 만약 바가 2개 미만이라면 답은 0이다. 
• 아니면 잘려져있는 문자열의 바 시작 인덱스와 마지막 바 인덱스, 그리고 총 바의 갯수를 구하여 정답을 도출한다.

바이너리 서치

• 우선 바의 인덱스들을 따로 저장한다.
• 그리고 바이너리 서치 bound로 첫 시작 바의 위치에 가까운 인덱스를 찾는다.
• 반대로 가장 오른쪽, 가까운 위치에 있는 바의 인덱스를 구한다.
• 만약 가까운 바의 인덱스인 시작, 끝 인덱스가 같다면 정답은 0이다.
• 반대로 바의 위치 오른쪽 인덱스에서 왼쪽 인덱스를 빼면 가까운 바 사이의 길이를 구한다. 
• 그리고 바갯수 (right - left)를 빼주고 별의 갯수를 구한다.

Pre Sum

• n + 1 크기의 배열 3개를 만든다.
• 첫번째로 left_bar는 문자열을 거꾸로 탐색하면서, 오른쪽에 있는 바들의 위치를 참고해가면서 인덱스를 저장한다.
• right_bar는 왼쪽부터 탐색하면서 왼쪽에 있는 바들의 위치를 참고해가면서 인덱스를 저장한다.
• pre_sum 배열은 지금까지 존재한 바들의 갯수를 더해간다.
• 이렇게 구한 배열들을 사용하여 정답을 구한다.
• left_bar에서 시작 인덱스를 넣으면, 이 배열은 오른쪽부터 탐색하여 오른쪽부터 쌓인 바들의 정보를 볼 수 있기 때문에, 현재 시작 인덱스에서 가장 가까운 오른쪽 인덱스를 찾을 수 있다.
• 반대로 right_bar에 끝 인덱스를 넣으면, left_bar와 다르게 반대로 탐색하여 바 인덱스를 넣어서, 현재 끝 인덱스에서 가장 가까운 왼쪽 인덱스를 찾을 수 있다.
• 만약 구한 인덱스의 크기가 오름차순이면, 위에서 구한 가까운 바 인덱스를 계산하여 길이를 구한다.
• 그리고, 바들의 갯수를 저장해놓은 프리썸에서 가까운 시작, 끝 바 인덱스를 넣어 현재 시작, 끝 인덱스사이의 바들의 갯수를 구한다.
• 전체 길이에서 바들의 갯수를 빼면 정답이 나온다. 

소스 코드

브루트 포스 : TLE = O(N^2)

st = '|**|*|*'
s, e = map(int, input().split())
temp = st[s - 1:e]
ans = 0
if temp.count('|') < 2:
    ans = 0
else:
    ans = temp.rfind('|') - temp.find('|') + 1 - temp.count('|')
print(ans)

바이너리 서치 : O(N + MlogM) -> O(NlogN)

# Binary Search
        def bs_left(arr, idx):
            l, r = 0, len(arr)
            while l < r:
                mid = l + (r - l) // 2
                if arr[mid] < idx:
                    l = mid + 1
                else:
                    r = mid
            return l
        
        def bs_right(arr, idx):
            l, r = 0, len(arr)
            while l < r:
                mid = l + (r - l) // 2
                if arr[mid] > idx:
                    r = mid
                else:
                    l = mid + 1
            return r
        
        
        candle = []
        res = []
        for i in range(len(s)):
            if s[i] == '|':
                candle.append(i)
        
        for start, end in queries:
            left = bs_left(candle, start)
            right = bs_right(candle, end)
            if left == right: res.append(0)
            else: res.append(candle[right - 1] - candle[left] - (right - left) + 1)
        return res

Pre Sum Fix : O(N + M)

# presum
        n = len(s)
        left_bar = [inf] * (n + 1)
        right_bar = [0] * (n + 1)
        pre_sum = [0] * (n + 1)
        res = []
        for i, v in enumerate(s):
            if v == '|':
                pre_sum[i + 1] = pre_sum[i] + 1
                right_bar[i + 1] = i
            else:
                pre_sum[i + 1] = pre_sum[i]
                right_bar[i + 1] = right_bar[i]
        for i, v in reversed(enumerate(s)):
            if v == '|':
                left_bar[i] = i
            else:
                left_bar[i] = left_bar[i + 1]
        for left, right in queries:
            left_close = left_bar[left]
            right_close = right_bar[right]
            close_length = right_close - left_close
            if l < r:
                ans = close_length - (pre_sum[left_close] - pre_sum[right_close])
            else:
                ans = 0
            res.append(ans)
        return res