[Python | 백준 1059번] 좋은 구간

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

1059번: 좋은 구간

 

문제

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

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

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

입력

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

출력

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

 

---

내 풀이

# 31252kb 112ms

먼저 집합 S 내에서 N이 어디에 있는지 구간 파악이 필요했다. 

S = [ 2, 3, 7, 9 ] , N = 4 라면 3과 7 사이라는 것을 찾아야했고, 

이때 N이 S의 첫번째 숫자 보다 작다면 (예를들어 N=1)이라면 0부터 2까지에 든다고 표시해야했다. 

 

그렇게 구간에 따라 N을 포함한 구간을 for문을 통해 반복했고, 

조건이 만족할때마다 cnt를 세어 주었다.

L = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
N = int(input())
cnt = 0

for i in range(L):
  if N < numbers[0]:
    a_range, b_range = 0, numbers[0]
    break
  if N >= numbers[i]:
    a_range, b_range = numbers[i], numbers[i+1]

if N in numbers:
  print(0)
else:
  for a in range(a_range+1, b_range):
    for b in range(a, b_range):
      if a != b and a <= N and N <= b:
        cnt += 1
  print(cnt)