코딩테스트 준비 - Maximum Product of Two Elements in an Array

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : LeetCode

• 문제 : Maximum Product of Two Elements in an Array

• 사용언어 : C#

• 난이도 : 최하

• 풀이시간 : 6m

• 유형 : 정렬, 시간복잡도, 배열

1464. Maximum Product of Two Elements in an Array

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Example 1:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

Example 2:

Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.

Example 3:

Input: nums = [3,7]
Output: 12

 Constraints:

• 2 <= nums.length <= 500

• 1 <= nums[i] <= 10^3

문제 풀이 접근

이 문제에 대한 접근 방법은 2가지가 생각났다.
1번. 리스트 돌면서 가장 큰 두개의 수를 찾아서 그 값을 -1 해서 곱한다.
2번. 어떤 리스트가 들어오던지 일단 정렬해서 2개를 찾는다.
(2번 일때, 오름차순 내림차순 상관없다. 그거에 맞게 인덱스를 뽑아오면 되기 때문)

그런데, 여태까지 풀어왔던 코딩테스트에서는 이런 문제가 주어질 때, 효율성까지 테스트하면 1번의 방법은 효율성에서 패스 못하는 경우가 많았던 것으로 기억해서 2번으로 방향을 잡았다.

이 문제의 플로우
1. 들어온 배열을 정렬한다. ( 오름차순으로 가정 )
2. 2개 이상은 꼭 들어온다는 것이 문제에 보장되어 있다. 그렇기 때문에,
(arr[arr.Length-2] -1) * (arr[arr.Length-1]-1); 을 연산해서 반환한다.

정답 작성 코드 (C#) - 오름차순

using System;
using System.Collections;

public class Solution {
    public int MaxProduct(int[] nums) {
        int answer = 0;

        Array.Sort(nums);
        answer = (nums[nums.Length-1]-1 ) * (nums[nums.Length-2]-1 );
        return answer;
    }
}

정답 작성 코드 (C#) - 내림차순

using System;
using System.Collections;

public class Solution {
    public int MaxProduct(int[] nums) {
        int answer = 0;

        Array.Sort(nums, (num1,num2) => num2.CompareTo(num1));
        answer = (nums[0]-1 ) * (nums[1]-1 );
        return answer;
    }
}

코드 결과