좋은 구간 - 파이썬 (정렬)

정렬에 관한 문제를 풀다가 스스로 문제를 해결한 백준 문제가 있어 제가 어떻게 풀었는지 공유를 하려고 합니다. 

 

사이트 링크 : https://www.acmicpc.net/problem/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에서 가장 큰 정수)

예제 케이스는 사이트에서 확인을 해보실수 있습니다

Input 
4
1 7 14 10
2
Output: [2,3], [2,4], [2,5], [2, 6]
4

Input
5
4 8 13 24 30
10
Output: # [9, 10], [9, 11], [9, 12], [10, 11], [10, 12]
5

 

문제 해설 

문제를 확인해 보면 알수 있듯이 집합 S에대한 요소에서 n이 들어갈 구간을 찾고 

그 구간에서 a <= x <= b 를 만족하는 개수를 찾으면 되는 문제이다 

문제 해결 포인트 

• n 이 주어진 S 요소에 어디 구간에 들어갈지 찾는것이 문제 해결 포인트였습니다.
• 단, 고민을 해야할 반례는 1,1000,1 로 1<=x<=999 x=1 을 만족하는 개수를 찾으면 됩니다. 
• 구간 개수를 찾는건 구간 리스트중 n의 인덱스를 찾고 리스트를 순회하면서 index 가 n의 인덱스보다 작을경우는 list[n:] 의 요소 개수를 더하고 index 와 n 이 같을 경우는 list[index+1:] 의 요소의 개수를 찾고 종료를 하면 됩니다.
• [9,10,11,12] => 9 일경우 (n=10) 10보다 작으므로 10,11,12 의 구간 개수(3개)
• [9,10,11,12] => 10 일경우 (n=10) 10 과 같으므로  11,12 의 구간 개수(3개)
• 생각을 해보면 구현하는건 어려운 문제는 아니였는데 생각지도 못한 반례가 있어 고민을 해야하는 문제 였습니다. 

문제를 푸는 단계를 나누면 아래와 같습니다. 

1. 집합 S를 내림 차순으로 찾고 구간의 start_point,end_point 를 찾는다 

2. 구간에 맞는 range를 생성하기 

3. range 에 맞는 [A,B] 의 개수 찾기 

1. 집합 내림차순 및 start_point,end_point 찾기 

S.sort()
# 좋을 구간을 찾을 start<=x<=end 를 찾을 값을 탑색
# start_point 찾는 함수
def get_start_point():
    global S
    start = 0
    while True:
        if n < S[start]:
            # 초기값이 0 일경우   1,10000,1 일경우 1<=x<=999 가 됨
            if start == 0:
                start = 0
            else:
                start -= 1
            break
        start += 1
    return start

# end_point 찾는 함수
def get_end_point(start):
    global S
    end = 0
    return end if n == S[start] else start+1

start = get_start_point()
end = get_end_point(start)

 

2. 구간에 맞는 range를 생성하기 

# start_num,end_num => start,end 에서 반례를 반영한 구간 시작과끝 정보 
# range num 구하기
# start_point 가 0 이고 S 집합 첫요소가 n 보다 크면 [1~S[start]] 구간 생성 
if start == 0 and n < S[start]:
    start_num = 1
    end_num = S[start]
else:
	# 그 외 케이스는 S요소의 +1 값의 start_num 작성 
    start_num = S[start]+1
    end_num = S[end]
# 해당 구간에 맞는 리스트 생성 
result_list = [i for i in range(start_num, end_num)]

 

3. range 에 맞는 [A,B] 의 개수 찾기 

if len(result_list) == 0:
    print(0)
else:
    idx = 0
    result = 0
    n_idx = result_list.index(n)
    while n_idx >= idx:
        if n_idx == idx:
            n_len = len(result_list[idx+1:])
            result += n_len
        else:
            n_len = len(result_list[n_idx:])
            result += n_len
        idx += 1
    print(result)

 

 

전체 해설 코드 

L = int(input())
S = list(map(int, input().split()))
n = int(input())
# 오름차순으로 집합 요소를 정리
S.sort()
# 좋을 구간을 찾을 start<=x<=end 를 찾을 값을 탑색
# start_point 찾는 함수
def get_start_point():
    global S
    start = 0
    while True:
        if n < S[start]:
            # 초기값이 0 일경우   1,10000,1 일경우 1<=x<=999 가 됨
            if start == 0:
                start = 0
            else:
                start -= 1
            break
        start += 1
    return start

# end_point 찾는 함수
def get_end_point(start):
    global S
    end = 0
    return end if n == S[start] else start+1

start = get_start_point()
end = get_end_point(start)

# range num 구하기
if start == 0 and n < S[start]:
    start_num = 1
    end_num = S[start]
else:
    start_num = S[start]+1
    end_num = S[end]

result_list = [i for i in range(start_num, end_num)]
if len(result_list) == 0:
    print(0)
else:
    idx = 0
    result = 0
    n_idx = result_list.index(n)
    while n_idx >= idx:
        if n_idx == idx:
            n_len = len(result_list[idx+1:])
            result += n_len
        else:
            n_len = len(result_list[n_idx:])
            result += n_len
        idx += 1
    print(result)