[Python] 1059번 : 좋은 구간

 

문제 설명이

복잡해보이지만 제한 조건과 예시를 보면

보다 쉽게 이해할 수 있다!

 

첫 줄은 집합 S의 크기,

두 번째 줄은 집합의 원소들,

세 번째 줄은 정수 n

 

따라서

크기가 4인 집합 S = [1, 7, 14, 10] 에서 2를 포함하는 좋은 구간을 구하라!

라고 해석할 수 있겠다.

 

좋은 구간의 원소들은

집합 S에 속하지 않으므로

[1,2]가 아닌 2부터 시작하고, A<B를 만족해야하기 때문에

[2,3] 부터 시작한다!

 

 

그럼

기본적인 입력 틀부터 작성

# 집합 S의 크기 L 입력
L = int(input())
S = []

# 집합에 포함될 정수 입력
idx = input()
answer = 0

if __name__ == '__main__' :
    # 입력 받은 정수 집합 S에 삽입 및 정렬
    for count in range(L):
        index = idx.split()
        S.append(int(index[count]))
    S.sort()
    
    # n 입력
    n = int(input())

S의 원소들을 삽입한 후,

값을 오름차순으로 정렬하여 작은 값부터 비교해볼 것이다!

 

	i = 0

	# 집합 S와 n 비교

	for i, compare in enumerate(S):
      
        # n이 집합 s의 원소와 같다면, 좋은 구간은 없다.
        if compare == n:
            print(answer)
            break
        
        # 제한 : n <= 집합 S에서 가장 큰 정수
        if compare > n:
            break

정수 n이 집합 S의 원소 중 하나와 같다면

좋은 구간은 만들어질 수 없으므로 0을 반환!

 

S의 i번째 원소가 n보다 커지는 순간 반복문을 멈추고

좋은 구간을 찾아보자!

 

	# n이 집합 S의 원소 사이에 있을 때 == 좋은 구간이 존재할 때
    if i != 0:
        if S[i] != n :
            # S[i-1] < n < S[i]인 경우
            if (n - S[i-1]) == 1:
                print(1*(S[i]-n-1))
            else :
                print((n-S[i-1])*(S[i]-n)-1)
                
    # 1 <= n < S[0] 인 경우
    if S[0] > n :
        if n == 1:
            print(1*(S[0]-n)-1)
        else :
            print(n*(S[0]-n)-1)

 

좋은 구간이 존재하는 경우에서

 

1. n이 원소 사이에 끼어 있는 경우

2. n이 1과 원소 사이에 끼어 있는 경우

 

두 가지 경우를 고려해줘야한다!

 

2번을 고려하지 않아

채점 과정 중에 몇 번 틀렸다.. 

 

좋은 구간의 개수는

앞서 했던 예시와 같이 경우의 수와

정수 n과 원소 사이의 차이만큼 곱해주는 방식으로 구하였다!

 

ex)

14 와 20 사이에 정수는 몇 개?

(20-14) -1 = 5개 

 

 

 

결과

 

짜잔