1208. [Python]부분수열의 합 2

1. 문제

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 이분 탐색
• 중간에서 만나기

 

3. 파이썬 코드

 

# input 값
N, S = map(int,input().split())
# 숫자 리스트
num_list = list(map(int,input().split()))
# 정렬
num_list.sort()
# 딕셔너리를 통해서 몇개 나왔는지 체크
answer_dict = {}
# 왼쪽 부분 합
left_sum = []
# 오른쪽 부분 합
right_sum = []
# 왼쪽 부분 합 구하는 로직
for i in range(N//2):
    left_length = len(left_sum)
    for j in range(left_length):
        left_sum.append(left_sum[j]+num_list[i])
    left_sum.append(num_list[i])
# 오른쪽 부분 합 구하는 로직
for i in range(N//2,N):
    right_length = len(right_sum)
    for j in range(right_length):
        right_sum.append(right_sum[j]+num_list[i])
    right_sum.append(num_list[i])
# 총 몇개의 S 가 나오는지 체크
cnt = 0

# 왼쪽 리스트를 순회하며 S인 경우 체크 및 딕셔너리에 왼쪽 리스트 값 추가
for i in left_sum:
    if i == S:
        cnt += 1
    if i in answer_dict:
        answer_dict[i] += 1
    else:
        answer_dict[i] = 1
# 오른쪽 리스트를 순회하며 S인 경우 체크
for i in right_sum:
    if i == S:
        cnt += 1
# 왼쪽 리스트 정렬, 오른쪽 리스트 정렬
left_sum.sort()
right_sum.sort()
# 왼쪽 리스트 길이 체크, 시작 인덱스, 오른쪽 리스트 시작 값 선택
left_length = len(left_sum)
left_index = 0
right_index = len(right_sum)-1
# 왼쪽 리스트 인덱스 값이 길이보다 작고 오른쪽 인덱스가 0 보다 크거나 같을때 까지
while left_index < left_length and right_index > -1:
    # 왼쪽 리스트 값 + 오른쪽 리스트 값이 S 보다 작으면 왼쪽 리스트 인덱스 +1
    if left_sum[left_index] + right_sum[right_index] < S:
        left_index += 1
    # 왼쪽 리스트 값 + 오른쪽 리스트 값이 S 보다 큰 경우 오른쪽 리스트 인덱스 -1
    elif left_sum[left_index] + right_sum[right_index] > S:
        right_index -= 1
    # 외의 경우 같을 때
    else:
        # cnt 값에 딕셔너리에 저장된 왼쪽 리스트 값의 개수를 증가
        cnt += answer_dict[S - right_sum[right_index]]
        # 오른쪽 리스트 크기가 더 크기 떄문에 -1
        right_index -= 1
print(cnt)

 

4. 문제를 풀고난 후 생각

 

• 중간에서 만나기 라는 알고리즘을 처음 접했다.
• 같은 문제를 분할 탐색과 비슷하게 나눠서 계산하여 시간 복잡도를 줄이는 알고리즘이다.
• 이 문제에서 2^40 의 시간 복잡도를 2^20 + 2^20 의 시간 복잡도로 나눠서 접근할 수 있도록 한 문제이다.
• 왼쪽 리스트, 오른쪽 리스트로 나눠준 후 각각 부분수열의 합을 모두 구해준 리스트를 생성한다.
• 생성한 리스트를 바탕으로 왼쪽 리스트 0 번인덱스 ~ 끝 과 오른쪽 리스트 끝 인덱스 ~ 0 번 까지 값을 비교해가며 S가 나오는지 체크를 해주면 된다.
• 만약 S에 도달 한 경우 왼쪽 리스트 값들을 미리 딕셔너리에 저장해뒀기 때문에 왼쪽 리스트 딕셔너리 값을 cnt 값에 증가시켜주면 S를 만드는 개수가 될 수 있다.
• 예외 사항으로 왼쪽 리스트, 오른쪽 리스트 값에 각각 구하고자 하는 S 가 이미 들어가 있는 경우도 사전에 체크해서 cnt 값을 확인해줘야 한다.

 

예시 => 5 0
-7 -3 -2 5 8
left_sum = [-10, -7, -3] ( 왼쪽 부분수열의 합 )

right_sum = [-2, 3, 5, 6, 8, 11, 13] ( 오른쪽 부분수열의 합 )

 

이미 앞서 부분을 나눠서 모든 부분 수열의 합을 구해뒀기 때문에 '부분 수열의 합 + 부분 수열의 합' 을 통해서 경우의수를 체크할 수 있다.

 

-10 과 13 을 더하면 3이 나오므로 right_index 값을 -1 해줘야 한다.

-10 과 11을 더하면 1이 나오므로 right_index 값을 -1 해줘야 한다.

-10 과 8 을 더하면 -2 가 나오므로 left_index 값을 +1 해줘야 한다.

 

이렇게 과정을 계속해 나가면 -3과 3에서 같은 값이 나오므로 이미 3은 answer_dict 에 {-7: 1, -10: 1, -3: 1} 가 있기 때문에 cnt 값이 1이 들어가며 정답으로 출력된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 이분 탐색
• 중간에서 만나기