[LeetCode] - 1920. Build Array from Permutation
LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Build Array from Permutation" 문제입니다.
--> https://leetcode.com/problems/build-array-from-permutation/description/
문제 :
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.
A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).
Example 1 :
Input : nums = [0,2,1,5,3,4]
Output : [0,1,2,4,5,3]
Explanation : The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]] = [0,1,2,4,5,3]
Example 2 :
Input : nums = [5,0,1,2,3,4]
Output : [4,5,0,1,2,3]
Explanation :
The array ans is built as follows: ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]] = [4,5,0,1,2,3]
Constraints :
- 1 <= nums.length <= 1000
- 0 <= nums[i] < nums.length
- The elements in nums are distinct.
Follow-up : Can you solve it without using an extra space (i.e., O(1) memory)?
이 문제를 보면, 주어진 배열 nums는 0에서 nums.length - 1까지의 정수를 포함하는 0 기반 순열입니다. 배열 ans를 ans[i] = nums[nums[i]]와 같은 방식으로 작성한 후 반환해야 합니다.
class Solution {
public int[] buildArray(int[] nums) {
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
ans[i] = nums[nums[i]];
}
return ans;
}
}
배열 속 인덱스를 잘 이해하고 응용할 줄 알면 풀 수 있는 간단한 문제였습니다. 이 문제 역시도 저 같은 초보들한테 추천드립니다.
이 코드는 주어진 nums 배열을 사용하여 새로운 배열 ans를 작성합니다. 각 인덱스 i에 대해 ans[i]는 nums[nums[i]]와 동일합니다. 이는 nums 배열의 값을 기반으로 새로운 배열을 생성하는 문제를 해결합니다.
- 배열 초기화 :
- int[] ans = new int[nums.length]; 문장을 사용하여 주어진 배열 nums와 동일한 길이의 배열 ans를 초기화합니다.
- 배열 값 설정 :
- for (int i = 0; i < nums.length; i++) { ... } 문장을 사용하여 배열 nums의 각 인덱스를 순회합니다.
- ans[i] = nums[nums[i]]; 문장을 사용하여 ans 배열의 각 인덱스 i에 대해 nums[nums[i]] 값을 설정합니다.
- 결과 반환 :
- return ans; 문장을 사용하여 최종 배열 ans를 반환합니다.
- 시간 복잡도 : O(n)
- 배열 nums를 한 번 순회하면서 새로운 배열 ans를 작성하므로, 시간 복잡도는 O(n)입니다. 여기서 n은 배열 nums의 길이입니다.
- 공간 복잡도 : O(n)
- 결과를 저장하기 위해 추가적인 배열 ans가 필요하므로, 공간 복잡도는 O(n)입니다. 이 배열은 입력 배열과 같은 크기를 가지므로, 추가적인 공간이 필요합니다.
문제는 Follow-up은 O(1)인 공간 복잡도를 추구하는데, 어떻게 하면 좋을까요?
이런 문제 특징은 막 저장값을 중간으로 나누고, 모듈로 사용하고 그래야 한다는 건데, 느낌만 알고 정확히 뭘 해야 할지는 몰라서 힌트를 얻어왔습니다.
바로 이 분의 코드와 설명인데, 정말로 기가 막히게 친절하게 써주셨으니, 한 번 확인하시기 바라겠습니다 : https://leetcode.com/problems/build-array-from-permutation/solutions/1692310/easy-explanation-for-o-1-space-complexity
또, 어떤 분은 Bit mask를 사용하셨는데, 솔직히 저는 그 방식 보다 이 분의 링크를 타고 설명을 보는 게 더 나을 거라고 생각됩니다.
