정수 array nums
가 주어질 때, 우리는 nums
를
0
~nums.length - 1
의 숫자i
를nums[i]
로 보내는 map
으로 여길 수 있습니다. 이 때 0
~ nums.length - 1
의 숫자 i
를 nums[nums[i]]
로 map하는 array를 return하는 문제입니다.
손 가는대로 풀면 다음과 같습니다.
class Solution {
public int[] buildArray(int[] nums) {
int[] memo = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
memo[i] = nums[i];
}
for (int i = 0; i < nums.length; i++) {
nums[i] = memo[nums[i]];
}
return nums;
}
}
다만 이 문제의 핵심은 다음 Follow-up입니다.
Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?
memo
의 내용을 nums
에 기록하는 방법은 없을까요? 도저히 방법이 떠오르지 않아 Solution(링크) 을 봤습니다.
(x, y) 형태의 array든 tuple이든 list든 x와 y
2가지 값을 저장할 때가 있습니다.(2차원 bfs 쓰는 문제 등)
저런 2차원 구조를 가진 자료형을 써도 되지만, java
문법이 상당히 귀찮은 이유로 종종 이 쌍을 x + y * n
으로 바꿔(x < n
보장될 때) int
값으로 저장했다가, 사용할 때는 값을 꺼내서 n으로 나눈 나머지
를 x
로 n으로 나눈 몫
을 y
로 사용하는 경우가 있었는데요. 이 문제에서 유용한 트릭입니다.
손 가는대로 푼 방식에서 memo
를 쓸 수밖에 없는 이유는, nums
를 순서대로 읽으며 진행할 때 nums[i] < i
인 경우, 이미 i
를 읽기 전에 nums[i]
를 먼저 읽은 상황이라 nums[i]
의 원래값은 날아가고 nums[nums[i]]
로 mapping 되어있어 실패하기 때문입니다.
그래서 num[i]
를 nums[nums[i]]
로 갱신할 때, 기존값(nums[i]
)을 함께 저장하는 것을 목표로 합니다. 위 트릭을 응용하면
nums[i] + nums[nums[i]] * n
where (nums[i] < n
)
으로 저장하면 되겠습니다. 그러면 저 값을 꺼내서 n으로 나누면 우리의 최종목표인 nums[nums[i]]
가 되고, 기존값인 nums[i]
가 필요하면 n으로 나눈 나머지를 쓰면 됩니다.
마침 문제에 0 <= nums[i] < nums.length
라는 조건이 있어서 n은 nums.length
로 설정하면 됩니다. 이런 조건이 없다면 저 위의 where절을 만족시키는 아주 큰 수를 쓰면 됩니다.
종종 사용하던 트릭인데 막상 불가결할 때 떠오르지 않아 아쉬웠습니다.
class Solution {
public int[] buildArray(int[] nums) {
int n = nums.length;
for(int i = 0; i < n; i++){
nums[i] = nums[i] + (nums[nums[i]] % n) * n;
}
for(int i = 0; i < n; i++){
nums[i] = nums[i] / n;
}
return nums;
}
}