[Algorithm] 백준 BOJ 1059 좋은 구간(python 파이썬)

BOJ 1059 좋은 구간

문제

정수 집합 S가 주어졌을때, 다음 조건을 만족하는 구간 [A, B]를 좋은 구간이라고 한다.

1. A와 B는 양의 정수이고, A < B를 만족한다.
2. A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.

시간 제한 : 2 초
메모리 제한 : 128 MB

입력

첫째 줄에 집합 S의 크기 L이 주어진다. 

둘째 줄에는 집합에 포함된 정수가 주어진다. 

셋째 줄에는 n이 주어진다.

출력

첫째 줄에 n을 포함하는 좋은 구간의 개수를 출력한다.

제한

* 1 ≤ L ≤ 50
* 집합 S에는 중복되는 정수가 없다.
* 집합 S에 포함된 모든 정수는 1보다 크거나 같고, 1,000보다 작거나 같다.
* 1 ≤ n ≤ (집합 S에서 가장 큰 정수)

예제 입력 1

4
1 7 14 10
2

예제 출력 1

4

예제 입력 2

5
4 8 13 24 30
10

예제 출력 2

5

예제 입력 3

5
10 20 30 40 50
30

예제 출력 3

0

예제 입력 4

8
3 7 12 18 25 100 33 1000
59

예제 출력 4

1065

풀이

l = int(input())
arr = list(map(int, input().split()))
n = int(input())
arr.insert(0, 0)  
arr.sort()

if n in arr: 
    print(0)
else:
    for i in range(l):
        if arr[i] < n < arr[i + 1]:  
            res = (n - arr[i]) * (arr[i + 1] - n) - 1
            print(res)
            break