[Python/파이썬] 백준 1059번 좋은 구간

×

1059번: 좋은 구간

 

문제

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

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

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

입력

첫째 줄에 집합 S의 크기 L이 주어진다. 둘째 줄에는 집합에 포함된 정수가 주어진다. 셋째 줄에는 n이 주어진다.

출력

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

제한

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

 

코드

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

arr = sorted(arr)
s, e = 0, l-1
left = -1
while s <= e:
    mid = (s+e)//2
    if arr[mid] == n:
        print(0)
        exit()
    elif arr[mid] < n:
        left = mid
        s = mid+1
    else:
        e = mid-1
if left == -1:
    ans = (n-1)*(arr[0]-n)+(arr[0]-n-1)
else:
    ans = (n-arr[left]-1)*(arr[left+1]-n)+(arr[left+1]-n-1)
print(ans)

우선 집합에 포함된 정수들을 저장한 arr를 오름차순 정렬하고 매개 변수 탐색을 이용하여 집합에 있는 어느 수들 사이에 n이 들어가는지 찾는다.

만약 집합에 있는 수 중 n과 같은 수가 있다면 n을 포함하는 좋은 구간은 없는 것이므로 0을 출력하고 프로그램을 종료한다. 집합의 수들 중 n보다 작은 수들 중 가장 큰 수의 인덱스를 찾아서 left에 저장한다.

 

이제 우리가 찾는 좋은 구간의 개수는 다음과 같다.

(arr[left] 초과 n 미만 수의 개수) × (n 이상 arr[left+1] 미만 수의 개수) + (n 초과 arr[left+1] 미만 수의 개수)

만약 집합에 n보다 작은 수가 없어서 left == -1이라면 1 이상 arr[0]-1 이하의 수들 중에 n을 포함하는 좋은 구간의 개수를 구하면 된다. 이 경우에는 위의 식에서 arr[left]를 0, arr[left+1]을 arr[0]으로 바꿔주면 된다.