정수형 배열에서 특정한 값 찾기 문제

오늘 풀었던 데일리코딩 문제를 복습해보려고 한다.

 

처음 약 20분 간 수도코드 작성 및 어떻게 구현하면 좋을지를 헤맸었지만 다행히 중간에 잘못된 점을 깨닫고 정해진 시간안에 풀었던 문제다.

 

문제

정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 합니다.

 

입력

인자 1 : arr

• int 타입을 요소로 갖는 임의의 배열

 

출력

• int 타입을 리턴해야 합니다.

 

주의사항

• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
• 배열의 요소는 음수와 0을 포함하는 정수입니다.
• 배열의 길이는 3 이상입니다.

 

입출력 예시

int output = largestProductOfThree(new int[]{2, 1, 3, 7});
System.out.println(output); // --> 42 (= 2 * 3 * 7)
 
output = largestProductOfThree(new int[]{-1, 2, -5, 7});
System.out.println(output); // --> 35 (= -1 * -5 * 7)

 

문제 풀이

public class Solution { 
    public int largestProductOfThree(int[] arr) {
    // TODO:
 
        //단순히 제일 큰 숫자 3개를 곱하는게 아니라 음수를 고려해야하네
        //지금 드는 생각은 arr요소 중에 음수가 2개 이상일 경우엔 음수들만 따로 모은 배열을 만드는게 좋아보이는데?
        int count = 0;
        ArrayList<> minusList = new ArrayList<>();
        for(int i = 0; i < arr.length; i++){
            if(arr[i] < 0) {
                minusList.add(arr[i]);
                count++;}
        }
        //음수들만 따로 모은 배열에서 절대값이 가장 큰 2개의 수를 곱해서 multiply에 선언
        if(count >= 2) {
            int multiply = 0;
            for(int i = 0; i < minusList.length; i++){
                if(minusList[i])
            }
        }
        // 아니야 지금 정렬을 안 하니까 자꾸 반복문을 쓰게되잖아 오름차순 정렬부터하자
    
 
        // 1. 가장 큰 요소를 할당할 biggest
        // 2. 두 번째로 큰 요소 secondbiggest를 선언하고
        // 3. 세 번째 큰 요소 thirdbiggest선언
 
        // arr을 반복문을 돌면서 가장 큰 요소는 biggest에 넣고
        // biggest을 뺀 새로운 배열 newArr을 복사해와서 반복문 돌릴건데
        //     가장 큰 값은 secondbiggest에 넣고
        //     그 다음 큰 값은 thirdbiggest에 넣고
 
        // multiply랑 second*third를 비교해서 더 큰 값을 biggest에 곱하고 리턴
    }
}

음수를 고려해야 하기 때문에 단순 숫자 크기가 큰 3개를 곱하는게 아니라는 것은 바로 알았고, 이를 통해

1.요소 크기 순 큰 값 3개(셋 모두 양수)를 곱한 값

2.3개 중 하나는 가장 큰 값, 2개는 요소 크기 순 가장 작은 값(둘 모두 음수)을 곱한 값

둘을 비교해서 더 큰 값을 리턴해야 한다는 것 까지도 유추할 수 있었다.

 

하지만 arr의 요소 중 음수들만 따로 모은 배열을 생성해서 그 중 가장 작은 값 2개를 구하려고 하다보니 계속되는 반복문에 걸려 버려서 너무 복잡하게 풀고 있는 것 같다고 생각하던 그 때, arr을 오름차순으로 정렬하면 훨씬 쉽게 구할 수 있다고 생각했다.

 

public class Solution {
    public int largestProductOfThree(int[] arr) {
        // TODO:
        //1.arr의 요소가 뒤죽박죽이니까 정렬하기(오름차순으로)
        Arrays.sort(arr);
 
        //2.arr의 요소 3가지를 곱해서 나올 수 있는 최대값 구하기
        //2-1.요소 3가지가 모두 양수인 경우, 오름차순이니까 length-1, -2, -3
        int candidate1 = arr[arr.length - 1] * arr[arr.length - 2] * arr[arr.length - 3];
        //2-2.요소 3가지 중 2가지는 음수라서 곱하면 양수가 되는 경우, 가장 큰 양수값과 가장 작고, 그보다 하나큰 음수값 둘을 곱하기
        int candidate2 = arr[arr.length - 1] * (arr[0]) * (arr[1]);
        //둘 중 더 큰 수를 리턴
        return Math.max(candidate1, candidate2);
    }
}

그 결과 생각했던 것 보다 훨씬 깔끔하고 부드럽게 코드를 짤 수 있었다.

이번 문제로 배열에서 숫자가 나올 경우 정렬을 활용하면 특정한 값을 좀 더 쉽게 찾을 수 있다는 것을 알 수 있었다.

 

 

+레퍼런스 코드와 달랐던 점

가독성을 위해 arr.length를 하나의 변수로 지정해 arr[arr.length - 1] 부분을 좀 더 보기 좋게 바꾸었다.