[백준 1059] 좋은 구간

문제

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

1059번: 좋은 구간

---

아이디어

먼저 입력으로 들어온 집합 S를 정렬해야 한다. 그 다음 집합 S에서 구할 수 있는 모든 구간을 고려한다.

예제 입력 4에서 주어진 3, 7, 12, 18, 25, 100, 33, 1000의 경우를 생각해보자.

 

S = {3, 7, 12, 18, 25, 33, 100, 1000}이기 때문에 좋은 구간의 후보는 [1, 2], [4, 6], [8, 11], [13, 17], [19, 24], [26, 32], [34, 99], [101, 999]라고 생각할 수 있다. (n이 max(S)보다 작거나 같기 때문에 1000보다 큰 경우는 고려할 필요가 없다.) 

• A ≤ x ≤ B를 만족하는 모든 정수 x가 집합 S에 속하지 않는다.

라는 조건 때문에 구간의 양 끝점은 S의 원소를 포함하지 않는, 즉 이웃한 두 원소 사이에 존재하는 자연수 집합이 된다.

 

이를 이용해서 좋은 조건의 후보가 될 수 있는 구간을 찾는다.

 

먼저 좋은 구간을 정의할 수 없는 경우에 대해서 알아보자.

만약 S의 원소 중에 n과 같은 값이 있다고 하면 좋은 구간은 항상 S의 원소를 포함하지 않기 때문에 이 경우는 좋은 구간을 만들 수 없다.

 

위의 경우를 제외하면 좋은 구간을 정의할 수 있게 된다. 

S[i] < n 이고, S[i+1]이라면 좋은 구간의 후보는 [ S[ i ] + 1, S[ i + 1 ] - 1 ]이 될 것이다. 

 

여기서 min(S) > n이면, [1, min(S)-1]이 좋은 구간의 후보가 되어야 한다. 하지만 위의 방식을 이용하면,

S[i] < n 이고, S[i+1] 을 만족하는 i가 존재하지 않아 좋은 구간의 후보를 찾을 수가 없게 된다. 

이 문제를 해결하기 위해 임의로 S에 0이라는 원소를 추가한다.

그러면 기존에 최솟값이었던 값보다 작으면서 0보다 큰 값으로 이루어진 구간을 정의할 수 있게 된다. 

 

이제 좋은 구간의 후보를 구했기 때문에 그 안에서 조건을 만족하는 좋은 구간을 찾아보자.

위의 예시를 그대로 사용하면 좋은 구간의 후보는 [34, 99]가 된다. 

좋은 구간이 되기 위해서는 n(이 예제에서는 59)을 포함해야 한다.

 

따라서 좋은 구간은

[34, 59], [34, 60], ..., [34, 99], [35, 59], [35, 60], ..., [35, 99], ..., [59, 99]

가 된다. 

어떻게 계산해야 하는가? 다음 조건을 고려해보자.

 

1. 시작점이 n보다 크면 좋은 구간이 될 수 없다.

> 좋은 구간의 시작점은 n 이하의 정수여야 한다. 

 

2. 끝점이 n보다 작으면 좋은 구간이 될 수 없다.

> 좋은 구간의 끝점은 n 이상의 정수여야 한다. 

 

3. A < B이기 때문에 길이가 1이 될 수 없다.

> 좋은 구간의 시작점과 끝점이 같은 경우는 제외해야 한다. 

 

즉, 시작점이 될 수 있는 값은 (34, 35, ..., 59)로 총 26개, 끝점이 될 수 있는 값은 (59, 60, ..., 99) 41개이다.

그리고 3번 조건, 즉 [59, 59]인 경우는 제외되기 때문에 26 × 41 - 1 = 1,065이다.

---

Solution

l = int(input())
lst = list(map(int, input().split()))
n = int(input())

idx = 0
cnt = 0

lst.append(0)
lst.sort()

if n in lst : 
    print(0)

else : 
    for i in range(len(lst)) : 
        if lst[i] < n and lst[i+1] > n : 
            idx = i
            break
    
    itv = list(range(lst[idx] + 1, lst[idx+1]))
    
    len_sp = len([i for i in itv if i <= n])
    len_ep = len([i for i in itv if i >= n]) 
    
    print(len_sp * len_ep - 1)