백준 1059 좋은 구간 (Python)

백준 1059 좋은 구간 (Python)

문제

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

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

집합 S와 정수 n이 주어질 때, n을 포함하는 좋은 구간의 개수를 구하는 프로그램을 작성합니다.

---

테스트케이스

🧩 테스트케이스 1

입력
4
1 7 14 10
2

출력
4

🧩 테스트케이스 2

입력
5
4 8 13 24 30
10

출력
5

🧩 테스트케이스 3

입력
5
10 20 30 40 50
30

출력
0

🧩 테스트케이스 4

입력
8
3 7 12 18 25 100 33 1000
59

출력
1065

---

문제 작동원리

1. 입력값 이해

첫 번째 줄: 집합 S의 크기 L

두 번째 줄: 집합 S에 포함된 정수들

세 번째 줄: 포함될 정수 n

예시 입력

4
1 7 14 10
2

이 경우 S = {1, 7, 10, 14}, n = 2 입니다.

2. 집합 정렬 및 위치 확인

S를 정렬합니다.

정렬된 S	1	7	10	14

2는 1보다 크고 7보다 작으므로 1과 7 사이에 있습니다.

3. n이 속한 구간 찾기

n = 2가 1과 7 사이에 있으므로, 가능한 숫자는

1보다 크고 7보다 작은 모든 정수: 2, 3, 4, 5, 6

이 중에서 A와 B를 선택해야 합니다.

단, A ≤ n ≤ B여야 하고, A < B입니다.

A는 2부터 6까지 가능한데, B는 A보다 커야 합니다.

가능한 경우를 모두 써보면:

A	B	구간
2	3	[2,3]
2	4	[2,4]
2	5	[2,5]
2	6	[2,6]

총 4개가 됩니다.

→ 그래서 답은 4입니다.

---

다른 예시로 이해하기

예제 2

입력
5
4 8 13 24 30
10

출력
5

정렬하면: 4, 8, 13, 24, 30

10은 8보다 크고 13보다 작습니다.

따라서 가능한 숫자 범위는 9, 10, 11, 12입니다.

이 숫자들로 좋은 구간 [A, B]를 만들 때,

n = 10이 포함되어야 하고, A < B입니다.

가능한 경우:

A	B	구간
9	10	[9,10]
9	11	[9,11]
9	12	[9,12]
10	11	[10,11]
10	12	[10,12]

총 5개입니다.

---

아이디어

1. 문제의 조건 정리

좋은 구간 [A, B]는 다음 두 가지 조건을 만족해야 합니다.

• A ≤ x ≤ B 인 모든 정수 x가 집합 S에 속하지 않아야 합니다.
• A < B 입니다.

즉, 구간 [A, B] 안에 집합 S에 있는 숫자가 단 하나라도 있으면 안 됩니다.

이 조건 때문에 구간을 아무렇게나 잡을 수 없으며, S의 원소들 사이에서만 구간이 만들어집니다.

2. 구간은 딱 한 가지 구간만 존재함

집합 S는 여러 숫자로 이루어져 있지만, 어떤 수 n이 들어갈 수 있는 유일한 빈 구간은 하나뿐입니다.

왜냐하면 S의 원소들은 오름차순으로 정렬했을 때, 각 원소 사이의 간격들이 겹치지 않기 때문입니다.

예시

n = 10일 때,

4 [8 13] 24 30

• 8은 n이 포함될 수 있는 구간의 왼쪽 경계값(가장 큰 작은 수)
• 13은 n이 포함될 수 있는 구간의 오른쪽 경계값(가장 작은 큰 수)

이 구간 [8, 13] 사이에는 n=10이 포함될 수 있습니다.

반례 예시 (두 구간이 될 수 없는 이유)

4 [8 13 24] 30

만약 오른쪽 경계를 24로 확장하면,

13이 이 구간 [8, 24] 안에 포함되어버립니다.

그러면 “A ≤ x ≤ B인 모든 x가 S에 속하지 않는다”는 첫 번째 조건을 위반합니다.

즉, 구간이 두 개 이상 존재할 수 없고 반드시 하나의 구간만 가능합니다.

3. 구간 내에서 n을 포함하는 경우의 수

이제 [8, 13] 사이의 모든 정수를 살펴보겠습니다.

가능한 수: 9, 10, 11, 12

n = 10이 포함되려면,

• A는 8보다 크고 n보다 작거나 같은 값
• B는 n보다 크거나 같고 13보다 작은 값

이어져야 합니다.

계산 과정

• n보다 큰 값의 개수: 13 - n = 3 (11, 12, 13 중 13은 제외해야 하므로 2)
• n보다 작은 값의 개수: n - 8 = 2 (9, 10)

그런데 [A, B] 구간을 셀 때 [n, n]은 제외해야 하므로 -1을 해줍니다.

따라서 구간의 개수는 다음과 같습니다.

( n - 왼쪽 최대값 ) × ( 오른쪽 최소값 - n ) - 1

예시 검증

[8, 13], n=10일 때

 (10 - 8) \times (13 - 10) - 1 = (2 \times 3) - 1 = 5 

즉, 가능한 구간은 다음과 같습니다.

A	B	구간
9	10	[9,10]
9	11	[9,11]
9	12	[9,12]
10	11	[10,11]
10	12	[10,12]

총 5개가 만들어집니다.

그러므로

좋은 구간의 개수는 언제나

 ( n - 왼쪽 구간의 최대값 ) \times ( 오른쪽 구간의 최소값 - n ) - 1 

로 계산할 수 있습니다.

이 공식은 n이 들어갈 수 있는 유일한 빈 구간 [left, right] 안에서

n을 포함하는 가능한 [A, B] 쌍의 개수를 정확히 계산합니다.

---

코드

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

left = 0
right = arr[L - 1]
cnt = 0
arr.sort()

if n in arr:
    print(0)
    exit()

for i in arr:
    if i < n:
        left = i
    if i > n:
        right = i
        break

print((n - left) * (right - n) - 1)

---

결론

1. 집합 S를 정렬하여 n이 들어갈 수 있는 위치를 찾습니다.
2. 왼쪽 경계(left) 는 n보다 작은 S의 최댓값, 오른쪽 경계(right) 는 n보다 큰 S의 최솟값입니다.
3. 좋은 구간 개수는 \( (n - left) * (right - n) - 1 \) 공식을 통해 계산합니다.
4. n이 S 안에 존재하면 0을 출력합니다.