ArrayList안의 ArrayList가 왜 텅 비어 있지??

기본적인 ArrayList

ArrayList는 잘 알려져있듯이 java.util에 들어 있는 class 중의 하나다. 배열과 다르게 크기를 조절할 수 있고 RandomAccess 인터페이스를 상속해서 내부 요소에 대한 O(1) (상수시간)에 가까운 탐색이 가능하다. 하지만 요소를 추가하거나 삭제할 때는 O(n)이 걸리기 때문에 많은 요소를 삭제해야 한다면 LinkedList와 같은 자료 구조를 사용하자. 다음과 같이 제네릭을 사용해 보통 새로운 ArrayList를 생성한다.

import java.util.ArrayList;

class Main {
    private static ArrayList<Integer> orders = new ArrayList<>();

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            orders.add(i);
        }

        System.out.println("orders = " + orders);
    }
}

위와 같이 생성하고 제네릭에 맞는 타입을 내부에 추가해줄때는 아무런 문제가 없다.

ArrayList안의 ArrayList

마찬가지로 ArrayList의 대한 제네릭을 ArrayList로도 지정할 수 있다. 다음과 같이 제네릭을 써서 지정하면 된다.

import java.util.ArrayList;

class Main {
    private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
}

하지만 다음과 같은 경우는 어떨까?

n 개의 집합에서 r개를 순서에 상관없이 뽑는 것을 조합이라 한다. 만약에 1, 2, 3, 4 총 4 개의 숫자 중 2개를 뽑는 연산을 한다면 결과는 [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4] 가 나와야 한다.

위 식을 자바에서는 다음과 같이 구현할 수 있다.

import java.util.ArrayList;

class Main {
    private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    private static void combination(ArrayList<Integer> list, int[] nums, int index, int count) {
        if (count == 0) {
            result.add(list);
            return;
        }

        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            combination(list, nums, i + 1, count - 1);
            list.remove(list.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        /* 
        4개중 2개를 뽑는다
         */;
        combination(new ArrayList<Integer>(), nums, 0, 2);

        System.out.println("result = " + result);
    }
}

그럼 결과는 예상한대로 나오는지 확인해보자.

어 그러면 원래 리스트도 텅 비어 있는게 아닌가요?

왜 그럴까? 곰곰히 생각해보자. 우리는 main 메소드 안에서 combination 메소드를 불러와서 실행시켰다. 하지만 결과물을 담는 result는 main 메소드 외부에 있다. 따라서 combination 메소드 안에 있는 list의 상태는 요소들이 계속 추가되지만 result에 추가 될때는 main 메소드에 추가될 당시의 new ArrayList<Integer>()인 상태이다.

ArrayList안의 ArrayList가 제대로 안담기는거 같아요.

따라서 위와 같은 문제를 해결하려면 아래와 같이 코드를 살짝만 바꿔주면 된다. combination에서 기존의 list를 그대로 추가하지말고 새로운 복사본 new ArrayList<>(list)을 만들어서 추가해주면 우리가 원하던 결과가 나온다.

import java.util.ArrayList;

class Main {
    private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    private static void combination(ArrayList<Integer> list, int[] nums, int index, int count) {
        if (count == 0) {
            result.add(new ArrayList<>(list));
            System.out.println(list);
            return;
        }

        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            combination(list, nums, i + 1, count - 1);
            list.remove(list.size() - 1);
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        /*
        4개중 2개를 뽑는다
         */;
        combination(new ArrayList<Integer>(), nums, 0, 2);

        System.out.println("result = " + result);
    }
}

참고글

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/ArrayList.html

https://stackoverflow.com/questions/25147799/java-arraylist-of-arraylist

기본적인 ArrayList

ArrayList안의 ArrayList

ArrayList안의 ArrayList가 제대로 안담기는거 같아요.

참고글

티스토리툴바