배열요소 한 칸씩 뒤로 밀기

크기가 6인 정수형 배열 data가 있다고 하자.

2

3

5

8

13

21

data배열이 위와 같다고 생각하고, 각 요소를 한 칸씩 오른쪽으로 이동시킨다면

 

21

2

3

5

8

13

이런 모습이 될 것이다.

 

 

굉장히 간단한 문제지만, 조금만 생각해보면 당황스러운 부분이 존재하는데

'어떻게 배열 요소를 옮길 것인가?'라는 부분이다.

 

예를 들어 data [0]을 무턱대고 data [1]로 덮어 씌운다면, 원래의 요소 data [1]은 그냥 없어진다.

즉, 이 문제를 해결하기 위해선 원래의 요소를 보관할 임시 보관장소(이하 임시 변수)가 필요하다는 사실을 알게 된다.

 

그런데 각 요소를 옮길 때마다 임시 변수를 사용하는 것은 매우 번거로운 문제일 것이다.

 

어떻게 해야 최대한 효율적으로 옮길 수 있을까? 아니 그전에 효율적이라는 건 어떤 면에서 효율적이라는 것일까?

내 대답은 임시 변수에 저장하는 횟수를 최대한 줄이는 것이 효율적이라고 하겠다.

조금 더 쉽게 접근하기 위해 배열의 크기를 줄여서 생각해보기로 했다.

 

2

3

배열의 크기를 2개로 줄여보았다. 이렇게 줄여보면, 배열의 양 끝인 data [0] 또는 data [1] 중에 하나를 골라 임시 변수에

저장하면 될 것이다. 즉, swap 알고리즘과 별다를게 없다. 그럼 3개는 어떨까?

 

2

3

5

배열의 크기가 2일 때와 마찬가지로 양 끝인 data[0] 또는 data [2] 중에 하나를 골라 임시 변수에 저장해 보기로 했다.

data [0] = 2를 임시 변수에 저장하고 data [2]를 data [0]으로 옮긴다면,

 

5

3

5

와 같은 모습이 된다. 여기에서 data[1]을 data [2]로 옮기면,

 

5

3

3

이 되고, 여기에 임시변수로 옮겨놓았던 2를 data [1]로 옮기면,

 

5

2

3

최종적으로 데이터를 하나씩 오른쪽으로 옮긴 꼴이 된다.

 

일반화를 시켜본다면, 크기가 N인 배열 data에서, data [0] 또는 data [N-1]의 데이터를 임시 변수로 옮긴 뒤, 

data [N-2]부터 인덱스를 감소시켜가며 차례대로 복사한다. 그리고 남은 요소에 임시 변수로 옮겨놓은 데이터를 옮기면 문제를 해결할 수 있다.

 

이를 자바 코드로 작성한다면

이와 같이 쓸 수 있다.

 

결괏값도 잘 나온 것을 확인할 수 있다.