[SWEA-1959][Python] 두 개의 숫자열

문제

N 개의 숫자로 구성된 숫자열 Ai (i=1~N) 와 M 개의 숫자로 구성된 숫자열 Bj (j=1~M) 가 있다.

아래는 N =3 인 Ai 와 M = 5 인 Bj 의 예이다.

 

Ai 나 Bj 를 자유롭게 움직여서 숫자들이 서로 마주보는 위치를 변경할 수 있다.

단, 더 긴 쪽의 양끝을 벗어나서는 안 된다.
 

서로 마주보는 숫자들을 곱한 뒤 모두 더할 때 최댓값을 구하라.

위 예제의 정답은 아래와 같이 30 이 된다.

 

 

 

제약 사항

N 과 M은 3 이상 20 이하이다.

 

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,

두 번째 줄에는 Ai,

세 번째 줄에는 Bj 가 주어진다.

 

출력

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

예제

[입력]	[출력]
10 3 5 1 5 3 3 6 -7 5 4 7 6 6 0 5 5 -1 1 6 -4 1 8 7 -9 3 ...	#1 30 #2 63 ...

 

문제 해결 방법

• 숫자가 담긴 2개의 리스트의 크기를 비교해서 길이가 긴 리스트를 @list_long@, 길이가 작은 리스트를 @list_short@로 설정해준다.

list_long, list_short = (list_a, list_b) if len(list_a) >= len(list_b) else (list_b, list_a)

 

• 위에서 구한 각각의 리스트에서 [0 ≤ x ≤ 길이가 긴 리스트의 길이(@len(list_long)@) - 길이가 작은 리스트의 길이(@len(list_short)@)] 범위의 숫자들을 각각 곱셈해주고 합해준 후, 그 결과값들을 리스트(@num_sum_list@)에 넣어준다.

num_sum_list = []

for i in range(len(list_long) - len(list_short) + 1):
    origin_items = list_short[:]
    target_items = list_long[i:i + len(list_short)]

    num_sum = 0
    for j in range(len(origin_items)):
        num_sum += origin_items[j] * target_items[j]

    num_sum_list.append(num_sum)

 

• 리스트 안의 요소들을 내림차순 정렬을 해준다.
• 그러면 해당 리스트의 첫 번째 요소가 각 요소들을 곱셈한 것들의 합의 최댓값이 되며, 이것을 정답으로 출력시켜준다.

# 최댓값 찾기
num_sum_list.sort(reverse=True)     # 내림차순 정렬

return num_sum_list[0]

 

• 최종 솔루션 코드는 아래와 같다.

def solution(list_a, list_b):
    list_long, list_short = (list_a, list_b) if len(list_a) >= len(list_b) else (list_b, list_a)
    
    num_sum_list = []

    for i in range(len(list_long) - len(list_short) + 1):
        origin_items = list_short[:]
        target_items = list_long[i:i + len(list_short)]

        num_sum = 0
        for j in range(len(origin_items)):
            num_sum += origin_items[j] * target_items[j]
        
        num_sum_list.append(num_sum)
    
    # 최댓값 찾기
    num_sum_list.sort(reverse=True)     # 내림차순 정렬
    
    return num_sum_list[0]

 

코드

def solution(list_a, list_b):
    list_long, list_short = (list_a, list_b) if len(list_a) >= len(list_b) else (list_b, list_a)
    
    num_sum_list = []

    for i in range(len(list_long) - len(list_short) + 1):
        origin_items = list_short[:]
        target_items = list_long[i:i + len(list_short)]

        num_sum = 0
        for j in range(len(origin_items)):
            num_sum += origin_items[j] * target_items[j]
        
        num_sum_list.append(num_sum)
    
    # 최댓값 찾기
    num_sum_list.sort(reverse=True)     # 내림차순 정렬
    
    return num_sum_list[0]


T = int(input())

for test_case in range(1, 1 + T):
    N, M = map(int, input().split())

    A_nums = list(map(int, input().split()))
    B_nums = list(map(int, input().split()))

    answer = solution(A_nums, B_nums)
    
    print(f"#{test_case} {answer}")

 

참고

• 난이도: D2