[알고리즘 문제] 해싱2 (Python / 파이썬)

문제

유니는 해싱에 대해 배우고 있다.길이가 N인 수열 A를 길이가 M인 해싱수열 B를 이용해 해싱하는 과정은 다음과 같이 진행된다.
A의 0~M-1번 인덱스의 값을 B의 0~M-1번 인덱스의 값과 순서대로 곱한 뒤 그 결과를 모두 더한다.A의 1~M번 인덱스의 값을 B의 0~M-1번 인덱스의 값과 순서대로 곱한 뒤 그 결과를 모두 더한다....
위 과정의 결과들을 나열하면 B를 이용해 A를 해싱했다고 볼 수 있다.수열 A, B가 주어질 때 해싱 결과 중 가장 큰 값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N, M이 공백으로 구분되어 주어진다.
각 테스트케이스의 두번째 줄에는 수열 A가 공백으로 구분되어 주어지고, 세번째 줄에는 수열 B가 공백으로 구분되어 주어진다. 수열에 포함된 수는 모두 절댓값이 100,000 이하인 정수다.
( 1 ≤ T ≤ 10, 1 ≤ M ≤ N ≤ 20 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 해싱값 중 최댓값을 출력한다.

---

문제 풀이

A배열에 앞에서부터 차례대로 B를 곱한 결과를 확인해야 하므로 

A의 시작이 될 수 있는 값은 0부터 n - m 까지 입니다. 

만약 n - m 보다 시작 값이 커지면 범위를 벗어나므로 불가능 합니다.

 

따라서 첫번째 for문을 A의 범위로 설정해주고 

두번째 for문은 0부터 m까지 설정하여 b의 0부터 m 까지 값과

a의 시작 값에 0부터 m을 더한 인덱스의 값을 곱해주어 그 결과를 

모두 더해주었습니다. 

 

다음 인덱스로 넘어가기 전, max() 함수를 이용해 최대값을 구해주었습니다.

이때 주의해야 할 점이 있습니다. 처음 초기 max_value 값을 -1e9로 해주었었는데

틀린 답이라고 나왔었습니다. 다시 문제를 차근차근 읽어보니

수열에 포함된 수는 모두 절댓값이 100,000 이하인 정수다.

라는 조건이 있었습니다. 따라서 나올 수 있는 값은 -1e9 보다 작으므로 

더 작은 값인 -1e11 로 설정해주었더니 정답 판정을 받았습니다.

---

My code

for tc in range(int(input())):
    n, m = map(int,input().split()) # A와 B의 길이

    a = list(map(int,input().split())) # 수열 A
    b = list(map(int,input().split())) # 수열 B

    max_value = -1e11
    for i in range(n - m + 1): # A의 시작 값 범위
        result = 0
        for j in range(m): # B의 원소 범위
            result += a[i + j] * b[j] # 곱한 결과를 모두 더해줌
        max_value = max(max_value, result) # 최대값 찾아줌
    
    print('#' + str(tc + 1), end = ' ')
    print(max_value)