리트코드 - 1920. Build Array from Permutation

리트코드 - 1920. Build Array from Permutation

 

정수 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(링크) 을 봤습니다.

 

 

---

2가지 값을 함께 저장하기

(x, y) 형태의 array든 tuple이든 list든 x와 y2가지 값을 저장할 때가 있습니다.(2차원 bfs 쓰는 문제 등)
저런 2차원 구조를 가진 자료형을 써도 되지만, java 문법이 상당히 귀찮은 이유로 종종 이 쌍을 x + y * n으로 바꿔(x < n 보장될 때) int 값으로 저장했다가, 사용할 때는 값을 꺼내서 n으로 나눈 나머지를 x로 n으로 나눈 몫을 y로 사용하는 경우가 있었는데요. 이 문제에서 유용한 트릭입니다.

 

 

---

nums[nums[i]]와 nums[i]를 함께 저장하기

손 가는대로 푼 방식에서 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;
    }
}