문제
정수 집합 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())
lst = list(map(int, input().split()))
target = int(input())
lst.sort()
answer = 0
for num in lst :
if num == target :
break
if num > target :
min = answer + 1
max = num - 1
break
answer = num
answer = (answer - min) * (max - answer + 1) + max - answer
print(answer)
해설
L = int(input())
lst = list(map(int, input().split()))
target = int(input())
lst.sort()집합의 크기를 L에, 집합에 속한 원소들을 lst에, 포함해야 하는 숫자를 target에 입력받는다.
원소들을 계산하기 좋게 정렬한다.
answer, min, max = 0
for num in lst :
if num == target :
answer = 0
break
if num > target :
min = answer + 1
max = num - 1
break
answer = num
answer = (answer - min) * (max - answer + 1) + max - answer
print(answer)좋은 구간의 개수를 저장할 answer, 범위의 최댓값과 최솟값을 저장할 max와 min을 0으로 초기화한다.
만약 num과 target이 같으면 범위가 num~num이기 때문에 좋은 구간이 없는 것이기 때문에 answer을 0으로 저장한 뒤 끝낸다.
만약 num이 target이 크면 min을 answer+1로, max를 num-1로 갱신한 뒤에 반복문을 끝낸다.
num이 target보다 작으면 answer에 num을 지속적으로 갱신한다.
반복문이 끝났다면 최솟값 * 최댓값 + 마지막 항(max - answer)을 통해 구간의 개수를 계산한다.