[백준] 1059번 > 좋은 구간

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을 포함하는 좋은 구간의 개수를 출력한다.

제한

• 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

 

---

 

풀이

논리짜는 것은 간단했는데, 생각보다 예외case를 찾는게 시간이 걸렸다.

코드를 보며 설명을 하겠다.

l = int(input())
s = list(map(int,input().split()))
n = int(input())
s.sort()
answer = 0
idx = 0
check = True
if n in s:
    print(0)
else:
    for i in range(l-1):
        if s[i] < n and n < s[i+1]:
            idx = i
            check = False
            break
    else:
        for i in range(1,s[idx]):
            for j in range(i+1,s[idx]):
                if i <= n and j >= n:
                    answer += 1
        print(answer)
    if not check:
        for i in range(s[idx]+1,s[idx+1]):
            for j in range(i+1,s[idx+1]):
                if i <= n and j >= n:
                    answer += 1
        print(answer)

n값이 s값으로 들어가있으면 좋은 구간이 없음.

 

n이 포함될 수 있는 범위를 찾아야한다. i번째와 i+1번째를 n과 비교하여 사잇값이면 break하고 빠져나옴.

여기서 check = False라는 경우는, 사잇값으로 들어가는 경우이다.

예를들어, s = [1, 3, 5] 이고 n = 2라면 n이 1과 3사이의 값이므로 빠져나온다.

이제 이중for문을 돌면서 구간을 모두 구하면 된다.

하지만 예외의 경우가 있다.

4

5 7 9 10

2

==> 이 경우에는 s의 최솟값보다도 n값이 작아 for문을 돌고도 break에 걸리지 않는다. 이 case는 for-else로 처리하였다.