백준 [1059] 좋은 구간 (Python3)

문제 링크 : https://www.acmicpc.net/problem/1059

1059번: 좋은 구간

2번 틀리고 해결한 문제, 이 문제에서 함정이 있는데, 예제만 보고 배열을 구성할 경우 20%에서 틀릴 것이다.

 

완전 탐색

입력 받은 집합 S를 오름차순 정렬해, N보다 처음으로 값이 큰 위치와 그 전 위치의 값을 각각 A, B라고 하자.
지문 범위에 맞추기 위해 A는 1 더하고, B는 1 뺀다.

만약, 정확히 일치하는 S의 원소가 있다면 0을 출력하고 프로그램을 종료한다.

 

최소 값이 A 부터 N - 1까지는 지정할 수 있는 최대 범위가 N ~ B이고,
최소 값이 N이면 지정할 수 있는 최대 범위는 N + 1 ~ B이다.

이를 통해 계산식을 만들어 제출하면 20% 까지는 맞는다.
이 20%에서 틀린 코드에 대한 반례는 다음과 같다.

 

4
10 20 30 40
5

답  : 24

 

문제에서 제한을 보면 n의 범위는 1 이상 max(S) 이하로 되있다.
즉, n이 집합 S 사이에 있지 않고, 저 왼쪽에 있을 수 있다는 것이다.

 

따라서, 배열 S를 입력받은 후, 0을 추가해서 N이 집합 S 사이에 있을 수 있게 해주면
위에서 만든 식이 제대로 수행되는 것을 확인할 수 있다.

 

코드

L = int(input())
nums = list(map(int, input().split()))
N = int(input())
nums.append(0)
nums.sort()

A, B = 0, 0
for i in range(len(nums)):
    if N < nums[i]:
        A = i - 1
        B = i
        break
    elif N == nums[i]:
        print(0)
        exit()
numA, numB = nums[A] + 1, nums[B] - 1
ans = ((N - 1) - numA + 1) * (numB - N + 1) + (numB - (N + 1) + 1)
print(ans)