[Java/알고리즘] ArrayList 사용시 주의할 점(reference)

https://leetcode.com/problems/subsets/ 문제를 풀면서 또 겪었던 실수?를 정리하려고 합니다.

 

문제는 어려운 문제가 아니었는데 실수를 하니까 당황을 하게 되더라구요.

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        
        dfs(nums, 0, new ArrayList<>(), ans);
        
        return ans;
    }
    
    public void dfs(int[] nums, int index, List<Integer> temp, List<List<Integer>> ans){
        System.out.println(temp);
        if(nums.length == index){
            ans.add(temp);
            return;
        }
       
        temp.add(nums[index]);
        dfs(nums, index+1, temp, ans);
        temp.remove(temp.size()-1);
        
        dfs(nums, index+1, temp, ans);
    }
}

위와 같이 간단히 코드를 짰습니다.

손으로 간단하게 recursion tree를 그리며 검증을 해봤는데 문제가 없어 보였습니다.

그런데 결과값을 구하면 아래와 같이 나왔습니다.

 

[[],[],[],[],[],[],[],[]]

 

뭐가 문제인가 생각하다가 또 C언어의 포인터 개념이 떠올랐습니다.

temp가 class의 객체이기 때문에 ans.add(temp)를 하면 사실은 ans에 temp의 주소값과 비슷한게 들어갈겁니다.

 

그래서 ans.add(temp)를 하는 순간에는 정확한 값이 들어가있으나.. 이후 재귀함수가 계속 수행되면서

temp.remove(temp.size()-1)을 계속 만나게 됩니다.

 

결국 최종적으로는 temp는 빈 배열이 되며

ans의 값으로 들어온 8개의 인자는 모두.. temp를 가리키게 됩니다. 그래서 결과가.. 위처럼 나왔던 것이죠.

 

//ans.add(temp); //잘못된 코드
ans.add(new ArrayList<>(temp));

ans에 들어가는 값은 추후에 변경이 되면 안되므로 위와 같이 temp와 동일한 값을 가지는 새로운 ArrayList를 만들어서 넣어주면 됩니다.