count-the-hidden-sequences
학습 키워드: 배열(array)
문제 링크: https://leetcode.com/problems/count-the-hidden-sequences/description/
문제 설명
다음은 차이 배열 differences가 주어졌을 때, 숨겨진 수열의 가능한 경우의 수를 찾는 문제입니다. 주어진 differences 배열은 길이가 n인 정수 배열이며, 연속적인 정수 쌍 사이의 차이를 설명합니다. 더 구체적으로, 숨겨진 수열 hidden이 있다고 할 때, differences[i] = hidden[i + 1] - hidden[i]입니다.
또한 lower와 upper라는 두 정수가 주어지며, 이는 숨겨진 수열의 값들이 포함될 수 있는 범위를 설명합니다. [lower, upper] 범위 내에서 가능한 숨겨진 수열의 개수를 반환하세요. 가능한 수열이 없으면 0을 반환합니다.
제한 조건
- n == differences.length
- 1 <= n <= 105
- -105 <= differences[i] <= 105
- -105 <= lower <= upper <= 105
문제 풀이
문제는 배열의 원소를 더하면서 가장 값이 작을 때와 클 때를 구해서 upper과 lower 사이의 범위 안에 있는 경우의 수를 구하면 된다.
첫번째 풀이를 낸 뒤 itertools 라이브러리에 해당 코드를 더 적합하게 풀 수 있는 코드를 찾아서 배웠다.
1. 나의 풀이(반복문, 변수저장 반복) (856ms)
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
max_val,min_val=0,0
total = 0
for diff in differences:
total+=diff
if diff>0:
max_val=max(max_val,total)
else:
min_val=min(min_val,total)
return max(0,(upper-max_val)-(lower-min_val)+1)2. iterator 사용 (823ms)
accumulate 함수(accumulate(iterable,func,initial))는 기본적으로 배열의 원소를 누적해서 더하는 작업을 한다. 이 문제에서는 func를 지정하지 않았기 때문에 기본적으로 덧셈이 수행되므로 func을 지정하지 않았다. initial 파라미터를 사용하여 0으로 설정했다.
from itertools import accumulate
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
arr = list(accumulate(differences,initial=0))
return max(0,upper - lower +1 -max(arr) + min(arr))코멘트
어제 풀었던 bitwise 문제랑 기본적인 골격은 비슷해서 풀이를 적는게 어렵진 않았다. 다만 코드를 너무 투박하게 짜서 같은 문제를 풀어도 실력차가 많이보이는 것 같다. 아직 pythonic한 코드를 짜기에 많이 부족한 것 같다잇
