[SWEA | Java] 1959번 두 개의 숫자열

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpoFaAS4DFAUq

SW Expert Academy

티어

소요 시간

11분

분류

브루트포스

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            st = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            int[] a = new int[n];
            int[] b = new int[m];

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < m; i++) {
                b[i] = Integer.parseInt(st.nextToken());
            }

            long res;
            if (n > m)
                res = solve(n, a, m, b);
            else
                res = solve(m, b, n, a);

            System.out.println("#" + test + " " + res);
        }
    }

    private static long solve(int biggerSize, int[] biggerArr, int smallerSize, int[] smallerArr) {
        long res = Long.MIN_VALUE;
        for (int i = 0; i <= biggerSize - smallerSize; i++) {
            long temp = 0;
            for (int j = 0; j < smallerSize; j++) {
                temp += biggerArr[i + j] * smallerArr[j];
            }
            res = Math.max(res, temp);
        }
        return res;
    }
}

코드 설명

이 문제는 난이도에 비해서 공을 좀 들인 문제다

가장 큰 변화라 함은 입출력이다

아무래도 입력과 출력이 방대하지 않다 보니 Buffer를 사용하는 것보다 Tokenizer나 System.out.println을 사용하는 것이 시간 복잡도나 메모리 상에서 효율적이어서 코드를 변경했다.

위 문제에서는 110ms정도 빠르다.

 

하나 고려했던 것은 답을 int가 아닌 long 범위로 설정한 것이다

각각의 수의 범위가 정해지지 않았었는데 최대나 최소가 각각 int의 최댓값이나 최솟값이 들어오지 않을까 예상을 했고 따라서 long으로 풀이했다.

문제 자체는 답이 int로 한정되어 있는 것 같고 시간 상에서도 long으로 하면 약간의 손실이 있지만 문제에서 알려주지 않은 이상 long으로 하는 것이 옳다고 판단하여 최종 코드는 수정하지 않았다.

 

계산 로직은 함수로 따로 빼서 작성하였고, n과 m 중 어떤 것이 큰 값인지 모르니 이를 나눠서 코드를 작성해야했는데 main문이 길어지는 것과 비슷한 코드가 중복되는 것을 방지하기 위해 solve의 파라미터를 다르게 넣어 호출하는 것으로 풀이했다.