[Baekjoon] 1059번 : 좋은 구간
1. 문제
https://www.acmicpc.net/problem/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에서 가장 큰 정수)
// 예제 입력 1
4
1 7 14 10
2
// 예제 출력 1
4 // [2,3], [2,4], [2,5], [2, 6]
// 예제 입력 2
5
4 8 13 24 30
10
// 예제 출력 2
5 // [9, 10], [9, 11], [9, 12], [10, 11], [10, 12]
// 예제 입력 3
5
10 20 30 40 50
30
// 예제 출력 3
0
// 예제 입력 4
8
3 7 12 18 25 100 33 1000
59
// 예제 출력 4
1065
2. 핵심 아이디어
- 규칙 잘 찾아내기
3. Python 문제풀이
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
t = int(input())
arr.append(0)
arr.sort()
result = 0
for i in range(len(arr) - 1) :
if arr[i] == t or arr[i+1] == t:
result = 0
break
elif arr[i] < t and t < arr[i+1] :
result = (t - arr[i]) * (arr[i+1] - t) - 1
break
print(result)
4. Java 문제풀이
댓글남기기