[BOJ] 1059번 좋은 구간(Python)

문제

해결방법

전체 리스트를 정렬하고 n이 들어갈 수 있는 구간의 두 값(section_f, section_b)을 구한다.

방법 1) 해당 구간에서 생길 수 있는 조합(2개선택)을 모두 구하고 n이 조합 구간에 포함되면 count +1씩 하면서 진행
방법 2) 수학적 계산을 이용한다. n이 포함된 조합은 section_b - section_f 와 동일, n이 포함되지 않은 조합은 (n-section_f)x(section_b-n) 이다. 두 값을 더해서 리턴.

만약 n이 정수 집합 중 가장 작은 값보다 작을 경우, 또는 L이 1인 경우를 생각해서 처음에 정수 집합에 0을 추가해준다.
(이거 때문에 채점20%에서 계속 틀려서 고생..)

그리고 정수 집합 내에 n과 동일한 값이 있는 경우는 0을 리턴.

실제구현

방법1

조합을 사용해서 전체 탐색

import sys
import itertools

def calculate(num_list, n):
    result = 0
    if n in num_list:
        print(result)
        return

    num_list = [0] + num_list

    num_list.sort()
    for idx in range(len(num_list)-1):
        section_f = num_list[idx]
        section_e = num_list[idx+1]
        if n in range(section_f, section_e):
            break

    ab_list = list(itertools.combinations(range(section_f+1, section_e),2))
    for tmp_ab in ab_list:
        if n in range(tmp_ab[0],tmp_ab[1]+1):
            result += 1

    print(result)

if __name__ == '__main__':
    count = int(sys.stdin.readline())
    num_list = list(map(int, sys.stdin.readline().split()))
    n = int(sys.stdin.readline())
    calculate(num_list, n)

방법2

수학적 계산 이용

import sys

def calculate(num_list, n):
    result = 0
    if n in num_list:
        print(result)
        return

    num_list = [0] + num_list

    num_list.sort()
    for idx in range(len(num_list)-1):
        section_f = num_list[idx]
        section_e = num_list[idx+1]
        if n in range(section_f, section_e):
            break

    section_f = section_f +1
    section_e = section_e -1

    result = (section_e - section_f) + (n-section_f)*(section_e-n)
    print(result)

if __name__ == '__main__':
    count = int(sys.stdin.readline())
    num_list = list(map(int, sys.stdin.readline().split()))
    n = int(sys.stdin.readline())
    calculate(num_list, n)