[백준]1059 - 좋은 구간 (Python)

문제

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

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

집합 S와 n이 주어졌을 때, n을 포함하는 좋은 구간의 개수를 구해보자.
첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.

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

입력

8
3 7 12 18 25 100 33 1000
59

접근

[3,7,12,18,25,33,100,1000] 

1. n은 1보다 크거나 같고 1000보다 작거나 같다.
2. n이 포함될 수 있는 구간의 개수는 0~3, 3~7, 7~12 ... 100~1000 총 8개이다.
3. 8개의 구간 중 주어진 n을 포함하는 구간을 찾는다.
4. 해당 구간에서 만들 수 있는 부분 구간 중 n을 포함하는 좋은 구간은 다섯 가지 조건을 만족해야 한다.
   • n이 구간의 시작이나 구간의 끝이 아니다.
   • 좋은 구간의 시작점이 전체 구간의 시작점보다 크다.
   • 좋은 구간의 시작점이 n보다 같거나 작다.
   • 좋은 구간의 끝점이 n보다 같거나 크다.
   • 좋은 구간의 끝점이 전체 구간의 끝점보다 작다.
5. 예를 들어 주어진 수가 16이라고 했을 때, 16이 포함되는 구간은 12~18구간이다. 이 중 16을 포함하는 좋은 구간은 다음과 같다.

[13,16],[14,16],[15,16],[13,17],[14,17],[15,17],[16,17]

6. [시작점 = (13,14,15,16), 끝점 = (16,17)]
7. 구간의 총개수는 (가능한 시작점 수 * 가능한 끝점의 수) - (시작점과 끝점이 같은 경우) 로 구할 수 있다.
   (4 * 2) - 1 = 7

풀이

L = int(input())
nums = list(map(int, input().split()))
target = int(input()) # == n

nums.append(0)
nums.sort()

A = 0
for i in range(len(nums)-1) :
    if nums[i] == target or nums[i+1] == target:
        A = 0
        break
    elif nums[i] < target and target < nums[i+1]:
        A = (target - nums[i]) * (nums[i+1] - target) - 1
        break

print(A)