개요
1300:K번째 수나 1637:날카로운 눈 문제를 풀면서 '일정하게 증가하는 수열에서 특정 값(x)보다 같거나 작은 값의 개수를 세는' 경우가 존재했다.
풀다보니 위 로직이 공식처럼 딱 들어맞는 것을 발견했고 이를 정리하고자 한다.
코드
우선 코드로 살펴보자.
아래 코드는 1637:날카로운 눈 문제를 해결하며 적용한 메서드를 간소화 한 코드다.
# x: 기준이 되는 수
# a: 수열의 시작값
# c: 수열의 최댓값
# b: 수열이 증가하는 범위
# x보다 작거나 같은 수의 개수를 구하는 함수이다.
def count_equal_or_lower(x, a, c, b):
if x < a: # 찾으려는 수가 수열의 최소값보다 작다면, 결과는 0이다.
return 0
# x, c 중에서 작은 값을 고른다.
# 주어진 수열(a부터 c까지의 b만큼 증가하는 수열)의 범위의 끝을 설정한다.
# 탐색 범위를 좁히는 것이다.
max_val = min(x, c)
# max_val이 탐색 범위의 최솟값(a) 미만이면 결과는 0이다.
if max_val < a:
return 0
length = max_val - a # a부터 max_val까지의 길이를 구한다.
count = length // b # 길이를 b로 나눈다. 이는 즉, 시작값(a)부터 끝값(max_val)까지 b만큼 점프해서 얼만큼 움직이는지 세는 것이다.
result = count + 1 # 맨 처음 값(a)는 점프에 포함되지 않았으므로 1을 더해 값을 보정한다.
return result각 코드에 대한 설명은 주석으로 설명했다.
그럼 이제 예시를 통해 이해해보자.
예시
예시 1: a=1, c=10, b=1
다음과 같은 수열이 있다고 가정해보자.
시작값(a): 1, 최댓값(c): 10, 증가비(1): 1이다.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
위 수열에서 7보다 같거나 작은 숫자는 [1, 2, 3, 4, 5, 6, 7] 이다.
우선 찾으려는 범위를 먼저 정해보자.
수열의 최댓값(c)과 기준이 되는 수(x) 중, 더 작은 값은 x이다.
따라서 수열 [1, 2, 3, 4, 5, 6, 7] 안에서 7보다 작은 수를 찾아야 하는 것이다.
여기서부터 핵심인데, 시작 지점인 첫 번째 인덱스(0)로부터 마지막 인덱스(6)까지 b만큼 증가해서 몇 번만에 갈 수 있는지 세면 된다.
위 수열에서는 b가 1이기 때문에 6번 이동하면 될 것이다.
그리고 첫 번째 인덱스에 해당하는 값은 횟수에 포함되지 않았으니 +1을 해주어 보정을 해준다.
예시 2: a=3, c=23, b=4
이번에는 [3, 7, 11, 15, 19, 23] 의 수열이다.
위 수열에서 기준값 x를 18로 설정해보자.
우선, 탐색 범위를 설정하자.
탐색 범위의 시작값은 3이고, 끝값은 min(18, 23) 이므로 18가 된다.
즉, [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] 내에서 찾게 되는 것이다.
이때에도 마찬가지로 3부터 18까지 b만큼 증가해서 몇 번만에 도착하는지를 세보자.
b는 4 이므로 3부터 시작해서 [7, 11, 15]를 통해 3번만에 도착할 수 있다.
여기서 맨 첫 번째 값인 3이 제외되었으니 +1을 해준다.
결과적으로 [3, 7, 11, 15] 의 수열이 도출되고 총 개수는 4가 된다.
놀랍게도 탐색하는 범위는 3부터 18까지였지만, 시작값부터 b만큼 증가하며 끝값까지 도달하기 위한 숫자들을 보니 모두 수열 [3, 7, 11, 15, 19, 23]에 포함되는 값들이 된다.