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

[문제 출처]

https://www.acmicpc.net/problem/1059

1059번: 좋은 구간

 

[문제 풀이]

 

집합 S와 n이 주어졌을 때, n을 포함하는 구간 중 집합 S에 포함된 정수가 포함되지 않은 구간을 구하는 문제이다.

 

조건을 만족하기 위해서는 집합 S를 오름차순으로 정렬하여,

집합 S의 원소 중에서 구간의 하한선과 상한선이 될 정수를 고르고 그 범위 내에서 구간을 정해야 한다.

 

그렇게 하한선과 상한선이 정해지면 구간의 개수를 세야 하는데,

경우는 2가지로 나눠질 수 있다. 

구간의 시작이 n보다 작은 경우와, n인 경우이다.

 

예를 들어 보자

S = [4, 8, 13, 24, 30]  

n = 10

이렇게 입력이 주어졌다고 하면

 

좋은 구간을 만족하는 모든 정수는 S의 원소가 포함되지 않아야 하기에 8과 13 사이여야 한다. 그래야 n도 포함이 가능하기 때문이다.

 

8보다 크고 13보다 작은 범위에서 좋은 구간을 찾아보면, => 9, 10 , 11, 12

 

1) 구간의 시작이 n보다 작은 경우

[9,10] , [9,11], [9,12]

 

2) 구간의 시작이 n인 경우

[10,11], [10,12]

 

이렇게 나눠진다.

 

1)을 구하기 위해서는 n보다 작은 수들의 개수와 n보다 크거나 같은 수들의 개수를 구해서 곱해주어야 한다.

1 x 3 = 3

 

2)를 구하기 위해서는 n보다 큰 수들의 개수를 구해줘야 한다.

2

 

따라서 좋은 구간의 개수는

💡 (n 보다 작은 수의 개수)  x (n보다 크거나 같은 수의 개수) + (n보다 큰 수의 개수) 이 된다. 💡

=> (n - 하한선 - 1) x (상한선 - n) + (상한선 - n - 1)

#1059

L = int(input())
S = list(map(int, input().split()))
n = int(input())

S.sort()

bottom = 0
top = 0
if n in S:
  print(0)
else: 
  for s in S:
    if s < n:
      bottom = s
    elif s > n:
      top = s
      break
  cnt = (n - bottom - 1) * (top - n) + (top - n -1)
  print(cnt)