BaekJoon 1059번: 좋은 구간 (Python)

---

1. Problem

---

2. Solution

import sys
import bisect

L = int(sys.stdin.readline())
S = list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
S.sort()
idx = bisect.bisect_left(S, n)
point = S[idx - 1] + 1
if idx == 0:
    point = 1
count = 0
if n >= max(S):
    print(0)
else:
    end = S[idx]
    for i in range(point, n + 1):
        for j in range(n, end):
            if i < j:
                count += 1
    print(count)

---

3. Detail

이 문제는 bisect.bisect_left() 함수를 이용하여 n이 삽입되어야 할 index를 구해서 이용하면 문제를 풀 수 있다. 이 때, bisect.bisect_left()를 사용하려면 list가 정렬되어있어야 하므로 S.sort()를 해주어 S list를 정렬해야한다.

S.sort()
idx = bisect.bisect_left(S, n)
point = S[idx - 1] + 1
if idx == 0:
    point = 1

위의 코드를 살펴보면 먼저 bisect.bisect_left(S, n)를 사용하여 S list에 n이 삽입될 index를 구한다. 그 후 S[idx - 1] + 1을 이용하여 S list에 포함되어 있는 값 중 n이 들어갈 index의 바로 왼쪽 값을 뽑아준 후 해당 값이 포함되지 않도록 +1을 해주어 start 지점인 point 변수에 할당해준다. 이 때, idx가 0일 때는 point 할당 과정에서 index가 -1이 되므로 조건을 달아 start 지점을 1로 변경해준다.

if n >= max(S):
    print(0)
else:
    end = S[idx]
    for i in range(point, n + 1):
        for j in range(n, end):
            if i < j:
                count += 1
    print(count)

위의 코드는 좋은 구간의 갯수인 count를 계산하는 부분이다. 이 때 n이 list S 안에 있는 값 중 가장 큰 값보다 크거나 같은 경우는 좋은 구간을 만족하는 경우의 수가 0이므로 0을 출력하도록 한다. n이 max(S)보다 작은 경우엔 S[idx]로 end 지점을 구하여 end 변수에 할당한다.