HOWTO · Java
Java에서 배열 이동
이 기사는 Java에서 배열 이동을 보여줍니다.
이 페이지의 내용
배열을 이동한다는 말은 서로 다른 두 가지 작업을 뜻할 수 있습니다. 회전은 요소를 원형으로 이동해 모든 요소를 보존합니다. 오른쪽으로 두 칸 회전하면 마지막 두 요소가 맨 앞으로 옵니다. 반면 앞부분 요소를 제거하면 더 짧은 시퀀스가 반환되고 제거된 값은 사라집니다. 배열의 모든 내용을 유지해야 한다면 회전을, 끝부분 요소만 처리하려면 건너뛰기를 선택하세요.
아래 예제는 별도 설명이 없는 한 오른쪽 회전을 사용합니다. 양수 거리는 오른쪽으로, 음수 거리는 왼쪽으로 회전하며, 배열 길이보다 큰 거리는 배열 길이로 나눈 나머지로 줄일 수 있습니다. 배열의 길이는 고정이므로, 새 배열을 반환하는 코드가 호출자의 원래 배열을 그대로 두려면 그 배열을 다시 할당하거나 수정하지 않아야 합니다.
예제는 독립적으로 실행할 수 있는 Java 프로그램이며, 저글링 알고리즘 예제에는 출력이 포함되어 있습니다.
회전을 원하는지 앞부분 요소 제거를 원하는지 선택하기
int[] 같은 기본형 배열이 필요하면 반복문이나 임시 배열을 사용하세요. 데이터가 이미 List이거나 참조형 배열을 리스트처럼 다룰 수 있다면 Collections.rotate()를 사용하세요. 다른 배열을 할당하지 않고 배열 자체를 수정해야 하며 코드가 더 복잡해도 괜찮다면 저글링 알고리즘을 사용하세요. 스트림의 처음 n개 요소를 버리려면 skip()를 사용하세요. 이는 회전이 아니며 원래 길이를 보존하지 않습니다.
반복문으로 배열을 제자리에서 회전하기
이 방법은 한 번에 오른쪽으로 한 칸씩 이동합니다. 다른 요소를 오른쪽으로 옮기기 전에 마지막 값을 저장한 다음, 저장한 값을 인덱스 0에 넣습니다. 예제는 정수 다섯 개로 시작해 오른쪽으로 두 칸 회전합니다. 전달받은 배열을 수정하고, 추가 공간은 상수만큼 사용하며, 길이가 n이고 정규화된 거리가 k인 배열에 대해 O(n × k) 시간이 걸립니다.
이 예제를 실행하세요:
이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
int distance = 2;
if (values.length > 0) {
int steps = Math.floorMod(distance, values.length);
for (int step = 0; step < steps; step++) {
int last = values[values.length - 1];
for (int i = values.length - 1; i > 0; i--) {
values[i] = values[i - 1];
}
values[0] = last;
}
}
System.out.println(Arrays.toString(values));
}
}
Math.floorMod는 양수와 음수 거리를 배열 길이보다 작고 0 이상인 값으로 정규화합니다. 길이 검사로 0으로 나누는 일을 막고 빈 배열을 변경하지 않습니다. 정규화된 거리가 0인 경우에도 배열은 바뀌지 않습니다. 이 반복 이동 방법은 거리가 작을 때 간단합니다. 배열이나 거리가 크다면 다음 두 배열 방법은 각 요소를 한 번씩만 이동합니다.
임시 배열에 회전 결과 저장하기
인덱스 대응 관계를 직접 적용하고 O(n)의 추가 저장 공간을 사용할 수 있다면 두 번째 배열을 할당하세요. 오른쪽으로 회전하려면 먼저 거리를 steps로 정규화해 음수 거리와 배열 길이보다 큰 거리를 처리합니다. 이전 인덱스 i에 있던 요소는 ((long) i + steps) % n 위치로 이동합니다. long 중간값을 사용하면 유효한 int 인덱스를 더할 때 발생할 수 있는 오버플로를 막습니다. 나머지 연산을 하기 전에 배열이 비어 있는지 확인하고, 비어 있으면 즉시 반환하세요.
이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
int distance = 2;
int[] rotated = new int[values.length];
if (values.length > 0) {
int steps = Math.floorMod(distance, values.length);
for (int i = 0; i < values.length; i++) {
int destination = (int) (((long) i + steps) % values.length);
rotated[destination] = values[i];
}
}
System.out.println(Arrays.toString(rotated));
}
}
목적지 계산식은 마지막 위치를 넘어간 인덱스를 처음으로 되돌립니다. Java 배열의 유효한 길이에 대해 long 합은 범위를 벗어나지 않습니다. 그 합을 나머지 연산하면 values.length - 1 이하의 목적지 인덱스가 나옵니다. 배열 길이로 나눈 나머지를 더하는 것은 일대일 대응이므로 각 원본 인덱스는 서로 다른 목적지에 대응하고 요소의 상대적 순서도 유지됩니다. 원본 배열은 바뀌지 않습니다. 새 배열을 원본 대신 사용하려는 경우 반환된 배열을 사용하세요.
Collections.rotate()로 리스트 회전하기
Collections.rotate()는 List를 대상으로 합니다. 양수 거리는 오른쪽으로, 음수 거리는 왼쪽으로 회전합니다. 참조형 배열에 Arrays.asList(array)를 적용하면 같은 배열을 기반으로 하는 크기 고정 리스트가 만들어집니다. 요소를 교체할 수 있고 회전도 되지만, 리스트에 요소를 추가하거나 제거할 수는 없습니다. 리스트를 다시 배열로 변환하면 별도의 배열이 만들어집니다. int[] 같은 기본형 배열은 Arrays.asList로 List<Integer>가 되지 않습니다. 값을 박싱하거나 배열 전용 알고리즘을 사용하세요.
이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
Integer[] values = {1, 2, 3, 4, 5};
List<Integer> list = Arrays.asList(values);
Collections.rotate(list, 2);
Integer[] rotated = list.toArray(new Integer[0]);
System.out.println(Arrays.toString(rotated));
}
}
여기서는 리스트와 values가 같은 요소 저장 공간을 참조하므로, 회전하면 배열의 요소 순서도 바뀝니다. 별도로 만든 rotated 배열에도 회전된 값이 들어 있습니다. 이 방법은 객체 배열과 리스트에 간결하지만 기본형 데이터를 래퍼 객체로 변환하면 박싱이 발생합니다.
저글링 알고리즘으로 제자리에서 회전하기
저글링 알고리즘은 배열을 여러 순환 주기로 나눕니다. 왼쪽으로 d칸 회전할 때 현재 인덱스의 값은 current + d 인덱스에서 가져오며, 배열 길이를 넘으면 처음으로 돌아갑니다. 코드에서는 오버플로 없이 다음 식으로 인덱스를 계산합니다. current >= n - d ? current - (n - d) : current + d. d는 0부터 n - 1까지 정규화되어 있으므로 결과도 0부터 n - 1 사이입니다. d가 0이면 current가 그대로 반환됩니다. 서로 독립적인 순환 주기의 수는 gcd(n, d)입니다. 각 주기에서는 값이 시작 인덱스로 돌아올 때까지 경로를 따라 이동합니다. 이 방법은 O(n)번 이동하고 O(1)의 추가 저장 공간을 사용하므로, 다른 배열을 할당하기 어려울 때 유용합니다.
이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
int rightDistance = 2;
int n = values.length;
if (n > 0) {
int rightSteps = Math.floorMod(rightDistance, n);
int leftDistance = (n - rightSteps) % n;
int cycles = gcd(n, leftDistance);
for (int start = 0; start < cycles; start++) {
int saved = values[start];
int current = start;
while (true) {
int next = current >= n - leftDistance
? current - (n - leftDistance)
: current + leftDistance;
if (next == start) break;
values[current] = values[next];
current = next;
}
values[current] = saved;
}
}
System.out.println(Arrays.toString(values));
}
private static int gcd(int a, int b) {
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
}
[4, 5, 1, 2, 3]
먼저 코드는 요청된 오른쪽 회전 거리를 rightSteps로 정규화한 다음, (n - rightSteps) % n으로 동일한 왼쪽 회전 거리를 계산합니다. 요소가 다섯 개인 배열에서 오른쪽 거리 2와 -2는 각각 오른쪽 두 칸과 세 칸으로 정규화되고, 이에 해당하는 왼쪽 거리는 각각 세 칸과 두 칸입니다. Integer.MIN_VALUE도 뺄셈 전에 정규화하므로 안전합니다. 왼쪽 회전은 각 순환 주기에서 다음 인덱스의 값을 읽으며, 배열 끝에 도달하면 처음으로 돌아갑니다. 코드의 조건식은 current와 leftDistance의 합이 n - 1을 초과할 때 두 값을 더하지 않도록 합니다. 어느 분기를 거치든 계산되지 않은 합이 Integer.MAX_VALUE를 넘을 수 있는 경우에도 결과는 0부터 n - 1 사이입니다. 순환 주기의 수는 gcd(n, leftDistance)입니다. 정규화된 거리가 0이면 gcd(n, 0)은 n이고 조건식은 current를 반환하므로 각 값은 바뀌지 않은 채 다시 기록됩니다. 길이 검사는 빈 배열에서 나머지 연산을 하기 전에 처리합니다. 반복문과 임시 배열 방법이 더 쉽게 유지 관리되므로, 상수 추가 공간이 실제로 필요할 때 저글링 알고리즘을 선택하세요.
Stream API로 앞부분 요소 건너뛰기
앞부분 값을 끝으로 순환시키지 않고 결과에서 제외하려면 skip()를 사용하세요. 나머지 요소가 들어 있는 스트림을 반환하므로 이를 배열로 변환하면 더 짧은 배열이 만들어지고 원본은 바뀌지 않습니다. 건너뛸 개수가 요소 수와 같거나 더 크면 빈 결과가 나옵니다. skip()에는 음수가 아닌 개수가 필요합니다. 호출자가 음수를 전달할 수 있다면 개수를 검증하거나 0 이상으로 제한하세요.
이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5};
long count = 2;
int[] remainder = Arrays.stream(values).skip(count).toArray();
System.out.println(Arrays.toString(remainder));
}
}
Arrays.stream(values)는 정수 스트림을 만들고, skip(count)는 처음 count개 요소를 제외하며, toArray()는 나머지를 새 기본형 배열에 모읍니다. 끝부분만 처리할 때 편리하지만 결과 배열을 할당하며, 모든 요소를 보존해야 하는 회전을 대신할 수는 없습니다.
