백준 1059번: 좋은 구간 문제 풀이

1. 문제 개요

백준 1059번 좋은 구간 문제는 특정 정수 (n)을 포함하지 않는 좋은 구간을 찾아, 그 안에서 (n)보다 작은 숫자와 큰 숫자 사이의 조합을 구하는 문제입니다.
주어진 숫자 리스트에서 (n)을 포함하지 않는 구간을 찾아 가능한 조합 수를 계산해야 하며, 수학적 사고와 간단한 구현을 요구합니다.

2. 접근 방법

1. 입력 데이터 처리 및 정렬
   입력받은 리스트를 정렬하고, 정렬된 리스트의 인접한 수를 사용하여 (n)이 속한 구간을 찾습니다.
2. 구간 계산
   • (l): (n)보다 작은 가장 큰 수 + 1
   • (r): (n)보다 큰 가장 작은 수 - 1
     이 구간을 기준으로 (n)을 포함하지 않는 조합을 계산합니다.
3. 조합 공식
   • (n)보다 작은 수에서 (n)보다 큰 수로 가는 조합: ((r - n + 1) \times (n - l))
   • (n)보다 큰 수끼리만 연결되는 조합: ((r - n))
     이를 더해 최종 결과를 도출합니다.

---

3. 구현 코드

아래는 Python으로 작성한 코드입니다.

# 입력 받기
L = int(input())  # 리스트 크기
number_list = list(map(int, input().split()))  # 주어진 리스트
n = int(input())  # 주어진 정수 n

# 리스트 정렬 및 양 끝 값 추가
number_list = [0] + number_list
number_list.sort()

# 초기 값 설정
answer = 0
l, r = n, n

# n이 속하는 구간 찾기
for i in range(len(number_list) - 1):
    if number_list[i] + 1 <= n <= number_list[i + 1] - 1:
        l = number_list[i] + 1
        r = number_list[i + 1] - 1
        break

# 가능한 조합 계산
answer = (r - n + 1) * (n - l) + (r - n)

# 결과 출력
print(answer)

---

4. 주요 개념 및 계산

(1) 구간 찾기
정렬된 리스트에서 (n)이 들어갈 하한과 상한을 결정합니다. 예를 들어, 리스트가 [7, 8, 9, 10, 11, 12, 13]이고 (n = 9)라면:

• (l = 8 + 1 = 9)
• (r = 10 - 1 = 9)

(2) 조합 계산 공식

1. (n)보다 작은 수((l))와 (n)보다 큰 수((r))의 조합 수: ((r - n + 1) \times (n - l))
2. (n)보다 큰 수들끼리의 조합 수: ((r - n))

(3) 예제 계산
입력:

6
7 8 9 10 11 12 13
9

1. 리스트 정렬 및 구간 찾기:
   • 정렬된 리스트: [0, 7, 8, 9, 10, 11, 12, 13]
   • (l = 8 + 1 = 9, r = 10 - 1 = 9)
2. 조합 계산:
   • 조합 수 = ((9 - 9 + 1) \times (9 - 9) + (9 - 9) = 0)
3. 결과: 0

---

5. 장단점

장점

• 시간복잡도: (O(L \log L))로, 리스트 정렬 후 반복문을 통해 효율적으로 문제를 해결합니다.
• 수학적 사고: 간단한 조합 공식을 활용해 문제 해결 능력을 키울 수 있습니다.

단점

• 리스트가 매우 크거나 (n)이 경계값에 가까울 경우, 구간 계산이 헷갈릴 수 있습니다.

---

6. 적용 예시

입력 예시

6
7 8 10 11 12 13
9

실행 과정

1. 리스트 정렬 및 구간 찾기:
   • 정렬된 리스트: [0, 7, 8, 10, 11, 12, 13]
   • (l = 8 + 1 = 9, r = 10 - 1 = 9)
2. 조합 계산:
   • 조합 수 = ((9 - 9 + 1) \times (9 - 9) + (9 - 9) = 0)
3. 결과: 0