자바의 배열을 사용하면서 조심해야 할 "복사"

뚝딱이·2023년 2월 12일

복사를 한 배열의 값이 이상하다 ?

오늘은 알고리즘 문제 중 DP를 공부하여 프로그래머스의 정수 삼각형 문제를 풀었습니다. 이미 문제의 풀이는 학습하였기 때문에 구현만 하면 되는 문제였는데요 .. 🤔

이상하게 건드리지 않은 부분의 값이 계속 바뀌는 일이 생겼습니다.
아무리 들여다 보아도 해당 배열은 주어진 값 빼곤 이후에 값이 바뀌는 일이 없는데, print로 찍어보니 값이 계속 바뀌고 있었습니다.

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {        
        int[][] dp = triangle;
        for(int i = 0; i < triangle.length-1; i++){
            for(int j = 0; j < triangle[i].length; j++){
                int leftValue = dp[i][j]+triangle[i+1][j];  
                if(leftValue > dp[i+1][j]){
                    dp[i+1][j] = leftValue;
                }
                
                int rightValue = dp[i][j]+triangle[i+1][j+1];
                if(rightValue > dp[i+1][j+1]){
                    dp[i+1][j+1]=rightValue;
                }
            }
        }
        return Arrays.stream(dp[dp.length-1]).max.getAsInt();

위의 코드가 바로 문제의 그 코드인데요, int[][] dp = triangle을 사용해 triangle을 dp에 복사해서 사용하고 있습니다. triangle의 각 행마다 열의 갯수가 다르고, (0,0)을 따로 복사하지 않기 위해 이렇게 복사를 했습니다.

실행을 하니 반환되는 값이 너무 큰 값이었습니다. 오잉 ? 문제의 풀이는 문제가 없고, 구현도 어려울 것이 없는 문제인데 ? 하고 print를 찍어보니 triangle의 값이 자꾸 커져 답에 변화를 주는 것이었습니다.

그런데 이상합니다. 위의 코드에서는 triangle의 값을 바꾸는 코드가 단 한 줄도 없습니다. 그렇다면 triangle의 값은 왜 변하는 것일까요 ?
print를 일일이 찍어보니, triangle의 값이 변하는 데 주기가 있습니다. 바로 dp의 값이 변할 때 입니다. 그 때 바로 '아차 !' 싶은겁니다.

배열의 값이 이상했던 이유

이 때 중요한 것은 우리가 사용한 것이 java의 배열이라는 것입니다. java의 배열은 객체이므로 힙 영역에 생성되고, 배열 변수는 힙 영역의 배열 객체를 참조하게 됩니다. 따라서 위의 triangle 배열 변수는 실제 값을 가진 객체의 참조값을 가지고 있습니다.

따라서 위와 같습니다. 문제에서 triangle은 [[7], [3, 8], [8, 1, 0]]와 같이 각 행마다 길이가 다르므로 위와 같이 triangle[0]과 triangle[1]이 다릅니다.
그럼 위에서 제가 했던 것 처럼 int[][] dp = triangle를 하면 어떻게 될까요 ?

위와 같이 dp는 triangle의 주소값이 복사되어 triangle이 가리키고 있는 객체를 참조하게 됩니다. 즉 둘은 하나의 객체를 같이 공유하고 있습니다. 하나의 객체를 같이 공유하고 있기 때문에 dp의 값이 바뀌면 triangle의 값도 바뀌는 것이 당연합니다.

이처럼 주소값만을 복사하는 것을 얕은 복사라고 합니다.

따라서 얕은 복사를 하려면 아래와 같이 주소값을 복사해 객체를 공유해서 사용할 수 있습니다.

int[] origin = new int[4];
int[] copy = origin;

그렇다면 데이터 값은 복사를 하되, 공유 하지 않고 새로운 객체에 그 값을 넣어 아래와 같이 사용하려면 어떻게 해야할까요 ?

이렇게 다른 객체에 복사를 하는 것을 깊은 복사라고 합니다.
먼저 일차원 배열에서 깊은 복사를 하는 방법을 알아보겠습니다.

일차원 배열에서의 깊은 복사

새로운 배열을 생성해 for문 돌리기

우리가 원하는 것 그대로 구현하면 됩니다.
copy라는 배열을 origin의 길이만큼 new로 생성해 for문을 돌리며 origin의 데이터를 copy에 넣으면 됩니다.

int[] origin = {1, 2, 3};
int[] copy = new int[origin.length];

for(int i = 0; i < origin.length; i++) {
	copy[i] = origin[i];
}

clone()

int[] origin = {1, 2, 3};
int[] copy = origin.copy();

위와 같이 배열.copy()를 사용하면 됩니다.

Arrays.copyOf(T[] original, int newLength)

int[] origin = {1, 2, 3};
int[] copy = Arrays.copyOf(origin, origin.length);

Arrays 클래스의 copyOf() 메서드를 사용할 수 있습니다. 파라미터를 이용해 시작 부터 원하는 지점(length)까지 복사가 가능합니다. 위의 코드에선 처음부터 끝까지 복사했습니다.

Arrays.copyOfRange(T[] original, int from, int to)

int[] origin = {1, 2, 3};
int[] copy = Arrays.copyOfRange(origin, 0, origin.length);

copyOf()에선 종료지점을 정할 수 있었다면 copyOfRange는 말 그대로 범위를 지정할 수 있습니다. 따라서 시작점과 종료지점 모두 정할 수 있습니다.

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

int[] origin = {1, 2, 3};
int[] copy = new int[origin.length];
System.arraycopy(origin, 0, copy, 0, origin.length);

src : 원본 배열
srcPos : 원본 배열에서 복사할 항목의 시작 인덱스
dest : 새 배열
destPos : 새 배열에서 붙여넣을 시작 인덱스
length : 복사할 개수
위와 같은 파라미터를 넣어 사용할 수 있습니다.

2차원 배열에서의 깊은 복사

2차원 배열은 위의 메서드들을 활용해도 깊은 복사가 되지 않습니다. 그 이유는 origin[i][j]가 있을 때 위의 그림에서 본 것 처럼 i가 j를 가리키고 있는 형태이기 때문입니다. 따라서 위의 메서드들을 사용하면 j를 가리키는 주소값이 있는 origin[i]만 복사되고 데이터가 있는 origin[i][j]는 깊은 복사가 되지 않습니다.

따라서 2차원 배열의 깊은 복사를 하는 법을 알아보겠습니다.

이중 for문 사용

1차원 배열에서 for문을 사용했던 것 처럼 구현하면 됩니다.

int[][] origin = {{1,2},{1,2}};
int[][] copy = new int[origin.length][origin[0].length];

for(int i = 0; i < origin.length; i++) {
	for(int j = 0; j < origin[i].length; j++ {
    	copy[i][j] = origin[i][j];
    }
}

메서드들 사용

2중 for문이 싫다면 for문을 하나만 사용하고, 1차원 배열에서 사용했던 메서드들을 사용하면 됩니다.

 	int[][] origin = {{1, 2}, {1, 2}};
    int[][] copy = new int[origin.length][origin[0].length];

    for (int i = 0; i < origin.length; i++) {
        copy[i] = origin[i].clone();
        //copy[i] = Arrays.copyOf(origin[i], origin[i].length);
        //copy[i] = Arrays.copyOfRange(origin[i], 0, origin[i].length);
        //System.arraycopy(origin[i], 0, copy[i], 0, origin.length);
    }