Jwanna Story

오늘도 알고리즘 문제를 풀다가 문제가 생겼다(?)

중복순열 가위바위보 문제를 구글링을 통해 순열 구현을 복사하고 이해하며 푸는 도중에...

위와 같은 끔찍한 광경을 보았다..

여튼 해당 문제가 발생한 이유는 값을 저장하는 배열이 얕은 복사가 되었기 때문이다.

문제가 발생한 코드는 아래와 같은데 해당 코드에서 잘못된 부분을 먼저 찾아봐도 좋을 것 같다.

    // 순열에 필요한 정보 : 출력할 result, 가위바위보 배열, result에 저장할 배열, depth, round
    public ArrayList<String[]> permutation(ArrayList<String[]> result,
                                           String[] arr, String[] out, int depth, int rounds) {
        // 탈출 조건 (Base case)
        // 저장한 배열이 rounds 까지 꽉차게 되면 result에 값을 저장하고 result를 리턴한다.
        if(depth == rounds) {
            result.add(out);
            return result;
        }

        // 반복문을 통해 arr 배열을 순회하면서 값을 입력한다
        for(int i = 0; i < arr.length; i++) {
            // out의 depth의 index에 rock, paper, scissors를 입력한다.
            out[depth] = arr[i];
            // 첫번째 index를 입력한 뒤 2번째 index를 입력하기 위해 depth+1을 하여 재귀 호출한다.
            permutation(result, arr, out, depth + 1, rounds);
        }
        return result;
    }

...

위에서 문제가 된 부분은

if(depth == rounds) {
    result.add(out);
    return result;
} 

해당 부분이다

result 리스트에 out 배열을 add 할 때 얕은 복사가 일어나면서

out 배열이 변경되는 것과 동시에 result 리스트에 add했던 모든 값들이 변경된 것이다.

❓  그래서 얕은 복사 / 깊은 복사가 뭔데?

얕은 복사란 실제 값이 아닌 객체의 주소 값을 복사해오는 것이다.

예를 들어 @5fa7e7ff라는 주소 값을 참조하는 객체 A가 있는데

B라는 객체에서 얕은 복사를 하게 되면 B도 @5fa7e7ff라는 주소 값을 참조하는 것이다.

위에서 했던 말을 다시 하자면,

같은 메모리 주소를 참조하기 때문에 실제 out의 값을 변경시키면 참조하고 있던 객체들의 값도 모두 변하게 된다.

반대로 깊은 복사는 실제 값을 새로운 메모리 공간에 복사하는 것이며,

위와 같은 상황에서 @5fa7e7ff의 주소 값을 참조하는 객체 A가 있는데

B라는 객체에서 깊은 복사를 하게 되면,

B는 실제 값을 @2d38eb89과 같은 새로운 메모리에 저장하게 된다.

조금 더 자세히 들어가지만 간단하게 덧붙이자면

위의 그림에서 노란색은 Stack 영역, 아래 파란색은 Heap 영역이라고 할 수 있고,

Stack 영역에서 객체 A, B가 각각 Heap 메모리의 실제 값을 참조하고 있는 것이라고 볼 수 있다.

❓ 아니 그래서 어떻게 해결하는데?

if(depth == rounds) {
    String[] fullArr = Arrays.copyOf(out, out.length);
    result.add(fullArr);
    return result;
}

간단하게 정답 먼저 공개하면 위와 같다.

out 배열을 직접 리스트에 삽입하는 것이 아닌

깊은 복사를 통한 새로운 배열을 만들어서 result에 삽입하면 된다.

참고로 깊은 복사를 위한 메서드로는 Object.clone(), System.arraycopy(), Arrays.copyOf() 등이 있는데

자세한 정보는 구글링 해보시길 .. ㅎ