[LeetCode] - 1646. Get Maximum in Generated Array

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Get Maximum in Generated Array" 문제입니다.

--> https://leetcode.com/problems/get-maximum-in-generated-array/description/

 

문제 : 

You are given an integer n.

A 0-indexed integer array nums of length n + 1 is generated in the following way :

• nums[0] = 0
• nums[1] = 1
• nums[2 * i] = nums[i] when 2 <= 2 * i <= n
• nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

Return the maximum integer in the array nums​​​.

---

Example 1 :

Input : n = 7

Output : 3

Explanation : According to the given rules :

• nums[0] = 0
• nums[1] = 1
• nums[(1 * 2) = 2] = nums[1] = 1
• nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
• nums[(2 * 2) = 4] = nums[2] = 1
• nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
• nums[(3 * 2) = 6] = nums[3] = 2 nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3

Hence, nums = [0,1,1,2,1,3,2,3], and the maximum is max(0,1,1,2,1,3,2,3) = 3.

 

Example 2 :

Input : n = 2

Output : 1

Explanation : According to the given rules, nums = [0,1,1].

The maximum is max(0,1,1) = 1.

 

Example 3 :

Input : n = 3

Output : 2

Explanation : According to the given rules, nums = [0,1,1,2].

The maximum is max(0,1,1,2) = 2.

 

Constraints: 0 <= n <= 100

---

이 문제는 주어진 규칙에 따라 길이가 n + 1인 배열 nums를 생성하고, 이 배열에서 가장 큰 값을 찾는 문제입니다. 배열 nums는 다음과 같은 규칙으로 생성됩니다:

1. nums[0] = 0
2. nums[1] = 1
3. nums[2 * i] = nums[i] (단, 2 ≤ 2 * i ≤ n)
4. nums[2 * i + 1] = nums[i] + nums[i + 1] (단, 2 ≤ 2 * i + 1 ≤ n)

이 규칙에 따라 배열을 채운 후, 배열의 최대값을 반환해야 합니다.

 

class Solution {
    public int getMaximumGenerated(int n) {
        int[] nums = new int[n+1];
        if(n==0)return 0;
        if(n==1)return 1;
        nums[0] = 0;
        nums[1] = 1;
        int max = 0;
        for(int i = 2; i <= n; i++) {
            if (i % 2 == 0) {
                nums[i] = nums[i/2];
            } else {
                nums[i] = nums[i/2 + 1] + nums[i/2];
            }
            max = Math.max(nums[i], max);
        }

        return max;

    }
}

 

이 코드는 사실상 주어진 문제의 조건을 잘 번역해서 쓴 코드입니다. 상세설명을 하자면 : 

1. 초기 조건 처리 :
   • n이 0이면 배열은 [0]이 되고 최대값은 0이므로 바로 반환합니다.
   • n이 1이면 배열은 [0, 1]이 되고 최대값은 1이므로 바로 반환합니다.
2. 배열 초기화 :
   • nums 배열을 크기 n+1n + 1n+1로 초기화하고, nums[0]을 0, nums[1]을 1로 설정합니다.
   • 최댓값을 저장할 max 변수를 0으로 초기화합니다.
3. 배열 채우기 :
   • for 루프를 사용하여 2부터 n까지 반복합니다.
   • i가 짝수일 경우 nums[i] = nums[i / 2]로 설정합니다.
   • i가 홀수일 경우 nums[i] = nums[i / 2 + 1] + nums[i / 2]로 설정합니다.
   • 각 값을 채울 때마다 최대값 max를 갱신합니다.
4. 결과 반환 :
   • 최종적으로 최대값 max를 반환합니다.

• 시간 복잡도 : O(n)
  • 배열을 채우기 위해 한 번 순회하며 각 요소를 계산합니다. 따라서 시간 복잡도는 O(n)입니다.

• 공간 복잡도 : O(n)
  • nums 배열은 크기 n+1n + 1n+1로 초기화되며, 이는 입력 크기에 비례한 공간을 사용합니다. 따라서 공간 복잡도는 O(n)입니다.

---

내 코드 Runtime 결과