[SW Expert Academy] 1959. 두 개의 숫자열

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpoFaAS4DFAUq&categoryId=AV5PpoFaAS4DFAUq&categoryType=CODE&problemTitle=%EB%91%90+%EA%B0%9C%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

Java 풀이

Scanner s=new Scanner(System.in);
        int tc=s.nextInt();
        for(int i=1;i<=tc;i++){
            int n=s.nextInt();
            int m=s.nextInt();
            int[] arr1=new int[n];
            int[] arr2=new int[m];
            for(int j=0;j<n;j++){
                arr1[j]=s.nextInt();
            }
            for(int j=0;j<m;j++){
                arr2[j]=s.nextInt();
            }
            int answer=0;
            if(n<m){
                for(int j=0;j<m-n+1;j++){
                    int sum=0;
                    for(int k=0;k<n;k++){
                        sum+=arr1[k]*arr2[j+k];
                    }
                    if(answer<sum){
                        answer=sum;
                    }
                }
            }else{
                for(int j=0;j<n-m+1;j++){
                    int sum=0;
                    for(int k=0;k<m;k++){
                        sum+=arr2[k]*arr1[j+k];
                    }
                    if(answer<sum){
                        answer=sum;
                    }
                }
            }
            System.out.printf("#%d %d\n",i,answer);
        }

내 생각

• 파이썬 풀이와 동일하다.
• 풀이시간 : 15분

---

Python 풀이

for tc in range(int(input())):
    n,m=map(int,input().split())
    arr_a=list(map(int,input().split()))
    arr_b=list(map(int,input().split()))
    answer=0
    if n<m:
        for i in range(0,m-n+1):
            sum=0
            for j in range(n):
                sum+=arr_a[j]*arr_b[i+j]
            answer=max(answer,sum)
    else:
        for i in range(n-m+1):
            sum=0
            for j in range(m):
                sum+=arr_b[j]*arr_a[i+j]
            answer=max(answer,sum)
    print("#"+str(tc+1)+" "+str(answer))

내 생각

• 긴 배열을 고정하고 짧은 배열을 이동시키면서 탐색하는 식으로 완전탐색 유형이라고 할 수 있다. 시간복잡도는 데이터 크기가 크지 않아 괜찮기 때문에 이중 for문을 사용하여도 된다. 각 배열의 길이가 작은것이 움직이도록 조건문을 걸어서 비교해준 후, 각 긴배열에의 짧은 배열의 비교의 시작점을 index로 두면서 합을 구하면 된다.
• 풀이 시간 : 10분