방구석프로의 이야기

https://school.programmers.co.kr/learn/courses/30/lessons/87390\

문제

문제 설명
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항
1 ≤ n ≤ 107
0 ≤ left ≤ right < n2
right - left < 105
입출력 예
n left right result
3 2 5 [3,2,2,3]
4 7 14 [4,3,3,3,4,4,4,4]

문제 해결을 위한 과정

이 문제의 핵심은 실제로 n * n크기의 2차원 배열을 선언하면 안 된다는 점입니다. n이 최대 10,000,000(10^7)이므로 실제로 배열을 만들면 시간 초과(TLE)가  발생합니다.

따라서 1차원 배열 상의 인덱스 값을 통해 2차원 공간의 행(row)과 열(col) 좌표를 수학적 접근을 통해 해결해야 합니다.

1. 정답 배열 크기 설정: 잘라낼 구간의 길이는 right - left + 1이 됩니다. 이를 정수형으로 형변환하여 answer 배열을 만듭니다.
2. 구간 순회: left부터 right까지 long 타입의 변수 i로 반복문을 돕니다.
3. 2차원 좌표 유추 (몫과 나머지):
   • 행(row): i / n을 계산하면 해당 칸이 몇 번째 행에 있는지 알 수 있습니다. 문제에서는 1행부터 시작하므로 + 1을 해줍니다.
   • 열(col): i % n을 계산하면 몇 번째 열에 있는지 알 수 있습니다. 마찬가지로 1열부터 시작하므로 + 1을 해줍니다.
4. 값의 규칙성 적용: 문제 그림을 분석해 보면 각 좌표에 들어갈 값은 Math.max(row, col), 즉 행 번호와 열 번호 중 더 큰 값이 채워진다는 규칙을 발견할 수 있습니다.
5. 이를 answer 배열에 차례대로 담아 반환합니다.

특별히 봐야할 문법

long 타입을 이용한 큰 수 제어 및 형변환: left와 right는 자바의 기본 int 범위를 넘어설 수 있는 long 타입으로 주어집니다. 그렇기 때문에 루프 제어 변수 i 역시 long으로 선언해야 안전합니다. 다만 i / n과 i % n의 연산 결과는 최종적으로 n(최대 10^7)보다 작으므로 안전하게 (int)로 강제 형변환하여 배열 인덱스로 활용할 수 있습니다.

for(long i = left; i <= right; i++) {
    int row = (int)(i / n) + 1;
    int col = (int)(i % n) + 1;
}

소스코드

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right - left +  1)];
        int index = 0;
        
        for(long i = left; i <= right; i++) {
            int row = (int)(i / n) + 1;
            int col = (int)(i % n) + 1;
            
            answer[index] = Math.max(row, col);
            index += 1;
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/70129

문제

문제 설명
0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

x의 모든 0을 제거합니다.
x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항
s의 길이는 1 이상 150,000 이하입니다.
s에는 '1'이 최소 하나 이상 포함되어 있습니다.
입출력 예
s result
"110010101001" [3,8]
"01110" [3,3]
"1111111" [4,1]
입출력 예 설명
입출력 예 #1

"110010101001"이 "1"이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.
회차 이진 변환 이전 제거할 0의 개수 0 제거 후 길이 이진 변환 결과
1 "110010101001" 6 6 "110"
2 "110" 1 2 "10"
3 "10" 1 1 "1"
3번의 이진 변환을 하는 동안 8개의 0을 제거했으므로, [3,8]을 return 해야 합니다.
입출력 예 #2

"01110"이 "1"이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.
회차 이진 변환 이전 제거할 0의 개수 0 제거 후 길이 이진 변환 결과
1 "01110" 2 3 "11"
2 "11" 0 2 "10"
3 "10" 1 1 "1"
3번의 이진 변환을 하는 동안 3개의 0을 제거했으므로, [3,3]을 return 해야 합니다.
입출력 예 #3

"1111111"이 "1"이 될 때까지 이진 변환을 가하는 과정은 다음과 같습니다.
회차 이진 변환 이전 제거할 0의 개수 0 제거 후 길이 이진 변환 결과
1 "1111111" 0 7 "111"
2 "111" 0 3 "11"
3 "11" 0 2 "10"
4 "10" 1 1 "1"

문제 해결을 위한 과정

주어진 문자열 s가 "1"이 될 때까지 무한 루프를 돌며 문제에 제시된 연산을 순서대로 수행하는 시뮬레이션 방식으로 접근했습니다.

1. 탈출 조건 설정: s.equals("1")을 검사하여 "1"이 되면 즉시 전체 루프를 빠져나갑니다.
2. 0의 개수 누적 및 1의 개수 카운트: 문자열 s를 한 글자씩 순회하며 0을 만나면 제거된 0의 총개수(num1)를 증가시키고, 1을 만나면 변환된 문자열의 길이를 뜻할 cnt를 증가시킵니다.
3. 남은 길이를 2진수로 변환: cnt 값을 2로 나눈 나머지(% 2)를 temp 문자열에 계속 더해주고 cnt를 2로 나누며( /= 2) 이진수 변환을 수행합니다.
4. 이진수 문자열 뒤집기: 뒤에서부터 연산된 2진수 값(temp)을 올바른 순서로 정렬하기 위해, 역순으로 순회하며 새로운 문자열 s를 재조립합니다.
5. 이 과정을 반복한 뒤 누적된 변환 횟수(num)와 제거된 0의 개수(num1)를 배열에 담아 반환합니다.

소스코드

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[2];
        int num = 0;
        int num1 = 0;
        
        while(true) {
            if(s.equals("1"))
                break;
            num += 1;
            int cnt = 0;
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == '1')
                    cnt += 1;
                else
                    num1 += 1;
            }   
            
            String temp = "";
            
            while(true) {
                if(cnt == 0)
                    break;
                temp += String.valueOf(cnt % 2);
                cnt /= 2;
            }
            
            s = "";
            for(int i = temp.length() - 1; i >= 0; i--) {
                s += String.valueOf(temp.charAt(i));
            }
        }
        
        answer[0] = num;
        answer[1] = num1;
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/131701

문제

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
3 ≤ elements의 길이 ≤ 1,000
1 ≤ elements의 원소 ≤ 1,000
입출력 예
elements result
[7,9,1,1,4] 18
입출력 예 설명


입출력 예 #1
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]

문제 해결을 위한 과정

이 문제의 핵심은 원형 수열을 어떻게 일반적인 선형 배열로 다룰 것인가? 입니다.

1. 원형 수열 선형화 (newArr): 원형 구조를 쉽게 처리하기 위해 원본 배열을 두 번 이어 붙인 elements.length * 2 크기의 새로운 배열(newArr)을 만듭니다. 나머지 연산(i % len)을 사용하면 원래 배열의 원소들이 순환하며 두 번 반복되어 담기게 됩니다.
2. 중복 제거용 자료구조 선택: 연속 부분 수열의 합 중 서로 다른 수의 개수를 세어야 하므로, 중복된 값을 허용하지 않는 HashSet 즉 집합을 사용합니다.
3. 연속 부분 수열 합 계산:
   • 바깥쪽 루프(i)는 부분 수열의 시작 인덱스를 결정합니다. 원래 배열의 길이(len)만큼만 돌면 모든 시작점을 체크할 수 있습니다.
   • 안쪽 루프(j)는 시작점 i부터 수열의 최대 길이인 i + len 직전까지 1씩 늘려가며 숫자를 하나씩 더해줍니다(sum += newArr[j]).
   • 숫자가 하나씩 누적될 때마다 set.add(sum)을 해줌으로써 길이가 1인 부분 수열의 합부터 길이가 len인 전체 수열의 합까지 자연스럽게 Set에 모두 저장됩니다.
4. 모든 루프가 끝나면 set.size()를 통해 중복이 제거된 순수한 합의 가짓수를 반환합니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        HashSet<Integer> set = new HashSet<>();
        int answer = 0;
        int len = elements.length;
        int len2 = elements.length * 2;
        int[] newArr = new int[len2];
        
        for(int i = 0; i < len2; i++) {
            newArr[i] = elements[i % len];
        }
        
        for(int i = 0; i < len; i++) {
            int sum = 0;
            for(int j = i; j < i + len; j++) {
                sum += newArr[j];
                set.add(sum);
            }
        }
        
        answer = set.size();
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=java

문제

문제 설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항
arr은 길이 1이상, 15이하인 배열입니다.
arr의 원소는 100 이하인 자연수입니다.
입출력 예
arr result
[2,6,8,14] 168
[1,2,3] 6

문제 해결을 위한 과정

처음에는 배열의 가장 큰 수(max)부터 시작해서 (int)1e9 즉 (10억)까지 숫자를 1씩 더하며 모든 원소로 나누어떨어지는지 확인하는 완전 탐색 방식으로 접근할 수 있습니다. 하지만 이 방식은 수의 규모가 커지면 시간 초과(TLE)의 위험이 있습니다.

따라서 정수론의 유클리드 호제법(최대공약수 구하기 공식)을 결합하여, 두 개씩 차례대로 최소공배수를 누적해 나가는 수학적 방식으로 해결했습니다.

1. 누적 연산 설계: 배열의 첫 번째 원소(arr[0])를 시작 정답으로 둡니다.
2. 배열 순회: 반복문을 돌며 현재까지 구한 누적 최소공배수(answer)와 다음 원소(arr[i])의 새로운 최소공배수를 구하여 answer를 갱신합니다.
3. 최소공배수 공식 활용: 두 수 A, B의 최소공배수는 (A * B) / 최대공약수(GCD)라는 수학적 공식이 성립하므로, 유클리드 호제법으로 최대공약수를 구한 뒤 대입합니다.
4. 이 과정을 배열의 끝까지 반복하면 n개 전체의 최소공배수를 구할 수 있습니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for (int i = 1; i < arr.length; i++) {
            answer = getLcm(answer, arr[i]);
        }
        
        return answer;
    }
    
    private int getGcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return getGcd(b, a % b);
    }
    
    private int getLcm(int a, int b) {
        return (a * b) / getGcd(a, b);
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=java

문제

문제 설명
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항
n은 1 이상, 2000 이하인 정수입니다.
입출력 예
n result
4 5
3 3
입출력 예 설명
입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

문제 해결을 위한 과정

이 문제는 작은 단위의 정답들이 모여 다음 큰 단위의 정답을 만드는 전형적인 동적 계획법(DP) 문제입니다. 직접 규칙을 써 내려가다 보면 익숙한 규칙을 발견할 수 있습니다.

• 1칸을 뛸 때 가짓수: 1 (1)
• 2칸을 뛸 때 가짓수: 2 (1+1, 2)
• 3칸을 뛸 때 가짓수: 3 (1+1+1, 1+2, 2+1)
• 4칸을 뛸 때 가짓수: 5

잘 보면 앞의 두 숫자를 더하면 다음 숫자가 되는 피보나치 수열의 형태를 띱니다. 즉, 점화식은 dp[i] = dp[i-1] + dp[i-2]가 됩니다.

1. 메모이제이션 배열 선언: 문제 조건에서 n은 최대 2,000까지 주어지므로 값을 저장할 dp 배열의 크기를 2001로 넉넉하게 잡아줍니다.
2. 초기값 설정: 1칸일 때의 방법 dp[1] = 1, 2칸일 때의 방법 dp[2] = 2를 먼저 채워줍니다.
3. 예외 처리: 만약 구하고자 하는 n이 1이거나 2라면 더 이상 계산할 필요 없이 초기값을 바로 반환합니다.
4. 반복문 수행 (Bottom-Up): 3부터 2,000까지 루프를 돌며 점화식에 맞게 배열을 채워나갑니다. 이때 값이 자료형 범위를 넘어가지 않도록 매번 1234567로 나눈 나머지를 저장합니다.

소스코드

import java.util.*;

class Solution {
    public long solution(int n) {
        long answer = 0;
        
        int[] dp = new int[2001];
        dp[1] = 1;
        dp[2] = 2;
        
        if(n == 1 || n == 2) {
            return dp[n];
        } 
        
        for(int i = 3; i <= 2000; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
        }
        
        answer = dp[n];
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12911

문제

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.
예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항
n은 1,000,000 이하의 자연수 입니다.
입출력 예
n result
78 83
15 23
입출력 예 설명
입출력 예#1
문제 예시와 같습니다.
입출력 예#2
15(1111)의 다음 큰 숫자는 23(10111)입니다.

문제 해결을 위한 과정

주어진 숫자 n부터 시작해 1씩 키워가며 모든 숫자의 이진수 1의 개수를 비교하는 완전 탐색 방식으로 해결할 수 있습니다.

1. 기준 1의 개수 구하기: 2진수 변환 원리인 2로 나눈 나머지(% 2)와 몫(/ 2)을 반복하여 원래 숫자 n의 이진수 1의 개수를 구합니다.
2. 숫자 1씩 증가시키기: n + 1부터 숫자를 1씩 계속 증가시키며 탐색합니다.
3. 1의 개수 비교: 증가시킨 숫자 역시 동일한 방식으로 이진수 1의 개수를 구한 뒤, 처음에 구해둔 기준 개수와 일치하는지 확인합니다.
4. 조건 만족 시 탈출: 최초로 1의 개수가 일치하는 숫자가 나오면 그 숫자가 조건을 만족하는 가장 작은 '다음 큰 숫자'가 되므로, 반복문을 빠져나와 정답을 반환합니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        int num1 = n;
        int numOfOne = 0;
        
        while(true) {
            numOfOne += num1 % 2;
            num1 /= 2;
            if(num1 == 0)
                break;
        }
        
        for(int i = n + 1; i <= 1000000; i++) {
            int numOfOne2 = 0;
            int num2 = i;
            boolean flag = false;
            while(true) {
                numOfOne2 += num2 % 2;
                num2 /= 2;
                if(num2 == 0) {
                    flag = true;
                    break;
                }
            }
            if(flag == true && numOfOne2 == numOfOne) {
                answer = i;
                break;
            }
        }
        
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12924

문제

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항
n은 10,000 이하의 자연수 입니다.
입출력 예
n result
15 4
입출력 예 설명
입출력 예#1
문제의 예시와 같습니다.

문제 해결을 위한 과정

연속된 숫자를 더해나가며 목표치인 n과 일치하는지 확인하는 '완전 탐색' 방식으로 접근하며 이 문제를 해결할 수 있습니다.

1. 시작점 고정 (바깥쪽 for문): 1부터 n까지 연속된 수열의 시작 숫자를 정해줍니다. (i)
2. 연속된 수 더하기 (안쪽 for문): 시작 숫자 i부터 1씩 커지는 숫자 j를 sum에 계속 누적해서 더해줍니다.
3. 조건 검사 및 가지치기:
   • sum > n: 더한 값이 이미 목표치 n을 넘어섰다면 더 이상 뒤의 숫자를 더할 필요가 없으므로 즉시 반복을 멈춥니다(break).
   • sum == n: 누적 합이 n과 정확히 일치하면 정답 카운트를 1 증가시키고, 역시 더 이상 더할 필요가 없으니 반복을 멈춥니다(break).
4. 이렇게 시작점을 옮겨가며 모든 경우의 수를 검사하여 최종 가짓수를 반환합니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i = 1; i <= n; i++) {
            int sum = 0;
            for(int j = i; j <= n; j++) {
                sum += j;
                if(sum > n) {
                    break;
                } else if(sum == n) {
                    answer += 1;
                    break;
                }
            }
        }
        
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/12941

문제

문제 설명
길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)
즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항
배열 A, B의 크기 : 1,000 이하의 자연수
배열 A, B의 원소의 크기 : 1,000 이하의 자연수
입출력 예
A B answer
[1, 4, 2] [5, 4, 4] 29
[1,2] [3,4] 10
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10)
이 경우가 최소이므로 10을 return 합니다.

문제 해결을 위한 과정

곱의 합을 최소로 만들기 위한 핵심 아이디어는 "한 배열에서 가장 큰 값은 다른 배열에서 가장 작은 값과 곱해져야 한다는 것"입니다. 큰 수끼리 곱해지면 숫자가 기하급수적으로 커지기 때문입니다.

1. 배열 정렬: 두 배열 A와 B를 Arrays.sort()를 이용해 오름차순으로 정렬합니다.
2. 엇갈려 곱하기:
   • A 배열은 앞에서부터(작은 값부터) 탐색합니다: A[i]
   • B 배열은 뒤에서부터(큰 값부터) 탐색합니다: B[n - i - 1]
3. 결과 누적: 엇갈린 두 값을 곱한 뒤 answer에 더해줍니다. 이 행동을 배열의 길이만큼 반복하면 수학적으로 가장 작은 최솟값이 도출됩니다.

소스코드

import java.util.*;

class Solution {
    public int solution(int []A, int []B) {
        int answer = 0;
        int n = A.length;
        
        Arrays.sort(A);
        Arrays.sort(B);
        
        for(int i = 0; i < n; i++) {
            answer += A[i] * B[n-i-1];
        }
        return answer;
    }
}