프로그래머스_최솟값 만들기

💻 문제 출처 : 프로그래머스_최솟값 만들기

👉 내가 작성한 답

import java.util.*;

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

        return answer;
    }
}

📌 문제 풀이 설명

• int 변수 answer를 선언하고 0으로 초기화
• int 변수 arrayLength에 A의 길이로 초기화
• A와 B 배열을 오름차순으로 정렬
• for문으로 0부터 arrayLength 미만까지 1씩 증가하며 순회
  • answer에 A[i]와 B[arrayLength - 1 - i]를 곱해서 더함
    • 인덱스로 계산하기 위해 배열의 길이에서 - 1을 함
    • 최소값과 최대값을 더해야 하기 때문에 가장 마지막 값을 곱해야 해서 arrayLength - 1에서 - i를 계산
    • ⇒ A는 1씩 증가하는 인덱스로 값을 가져오고 B는 가장 마지막 값에서 1씩 감소하는 인덱스로 값을 가져옴
• for문 종료 후 return answer
  
  
  
  

👉 다른 사람이 작성한 답

import java.util.*;

class Solution {
    public int solution(int []A, int []B) {
        int answer = 0;
        int length = A.length;

        quickSort(A, 0, A.length-1);
        quickSort(B, 0, B.length-1);

        for(int i = 0 ; i < length ; i++)
        {
            answer += A[i] * B[length-1-i];
        }

        return answer;
    }

    public static void quickSort(int[] arr, int left, int right) {
        int i, j, pivot, tmp;

        if (left < right) {
            i = left;
            j = right;
            pivot = arr[left];
            
            //분할 과정
            while (i < j) {
                while (arr[j] > pivot) j--;
                while (i < j && arr[i] <= pivot) i++;

                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
            arr[left] = arr[i];
            arr[i] = pivot;
            
            //정렬 과정
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }
}

📌 문제 풀이 설명

• 퀵 정렬 구현한 코드
• int 변수 answer를 선언하고 0으로 초기화, length를 선언하고 A의 길이로 초기화
• quickSort 메서드에 A 배열과 0, A의 길이 - 1(마지막 인덱스)를 인수로 넣어 실행하고 B 배열과 0, B의 길이 - 1을 인수로 넣은 것도 실행 ⇒ A와 B 배열을 오름차순으로 정렬
  • quickSort 메서드
    • 인자로 int 배열, int 변수 left, right를 받음
    • int 변수 i, j, pivot, tmp를 선언
    • 만약 left가 right보다 작으면
      • i에 left를 대입하고 j에 right를 대입
      • pivot에 arr[left]를 대입
      • while문으로 i가 j보다 작은 경우 순회
        • while문으로 arr[j]가 pivot보다 큰 경우 순회
          • j를 1 감소시킴
          • 오른쪽에서 왼쪽으로 이동하면서 pivot보다 작거나 같은 값을 찾음
          • 이 반복문이 종료되면 j는 피벗보다 작거나 같은 값을 가리키게 됨
        • while문으로 i가 j보다 작고 arr[i]가 pivot보다 작거나 같은 경우 순회
          • i를 1 증가시킴
          • 왼쪽에서 오른쪽으로 이동하면서 pivot보다 큰 값을 찾음
          • 이 반복문이 종료되면 i는 피벗보다 큰 값을 가리키게 됨
        • while문 종료 후 arr[i]의 값과 arr[j]의 값을 교환
          • tmp에 arr[i]를 대입하고, arr[i]에 arr[j] 대입 후 arr[j]에 tmp 대입
      • while문 종료 후 arr[left]에 arr[i] 대입, arr[i]에 pivot 대입
        • 피벗을 올바른 위치에 놓는 과정
        • 이 단계가 시작되기 전에, 배열은 크게 두 부분으로 나눠져 있을 것
          • 인덱스 left부터 i-1까지의 값들은 피벗보다 작거나 같음
          • 인덱스 i+1부터 right까지의 값들은 피벗보다 큼
          • pivot = arr[left]로 설정했으므로, 피벗은 배열의 left 인덱스에 있음
          • arr[i]는 피벗보다 작거나 같은 값이며, arr[left]는 피벗으로 두 값을 교환하면 피벗이 올바른 위치에 놓이게 됨
    • 재귀로 quickSort에 arr, left, i - 1을 인수로 전달하고, arr, i + 1, right도 인수로 전달해서 실행
      • 재귀적으로 퀵 정렬을 호출하여 왼쪽과 오른쪽 부분 배열을 정렬
• for문으로 0부터 length 미만까지 1씩 증가하며 순회
  • answer에 A[i]와 B[length - 1 - i]를 곱해서 더함
    • A는 1씩 증가하는 인덱스로 값을 가져오고 B는 가장 마지막 값에서 1씩 감소하는 인덱스로 값을 가져옴
• for문 종료 후 return answer