문제 링크 : 배열 회전 시키기
알고리즘 문제를 풀 때 단순히 기능을 구현하는 것을 넘어 성능과 메모리 효율을 고려해 코드를 개선하는 과정을 기록합니다. 이번에는 '배열 회전 시키기' 문제를 통해 단계별로 최적화를 진행했습니다.
1. 초기 접근: Deque 사용
처음에는 요소의 이동이 빈번하다는 생각에 Deque 자료구조를 떠올렸습니다.
Deque<Integer> dq = new LinkedList<>();
for(int i : numbers) dq.offerLast(i);
if (direction.equals("right")) {
dq.offerFirst(dq.pollLast());
} else {
dq.offerLast(dq.pollFirst());
}문제점은 Deque와 LinkedList라는 객체를 생성하는 과정에서 오버헤드가 발생했습니다. 원본 배열의 모든 요소를 LinkedList 노드 단위로 새로 할당해야 했기에 메모리 사용량이 비효율적이었고 결과 배열로 다시 옮기는 과정에서 부가적인 연산이 추가되었습니다.
성능 및 메모리는 테스트당 약 0.25ms ~ 0.31ms가 소요되었으며 불필요한 객체 생성으로 인해 메모리 자원을 낭비하고 있었습니다.
2. 성능 개선: 배열 직접 조작
자료구조를 생성하는 대신 원본 배열을 직접 인덱싱하여 결과 배열로 옮기는 방식을 선택했습니다.
if(direction.equals("left")){
for(int i=0; i<numbers.length-1; i++) {
answer[i] = numbers[i+1];
}
answer[numbers.length-1] = numbers[0];
} else {
for(int i=1; i<numbers.length; i++) {
answer[i] = numbers[i-1];
}
answer[0] = numbers[numbers.length-1];
}별도의 자료구조를 생성하지 않고 기존에 할당된 배열 내에서 인덱스 이동만 수행했습니다. 이로 인해 객체 생성 오버헤드가 사라졌습니다.
성능 및 메모리는 실행 속도가 0.01ms ~ 0.04ms 수준으로 Deque를 사용했을 때보다 약 10배 이상 빨라졌습니다. 메모리 또한 힙 영역에서의 객체 할당이 최소화되어 훨씬 효율적이었습니다.
3. 최종 완성: System.arraycopy 활용
마지막으로 배열 복사를 위한 내장 메서드인 System.arraycopy를 도입해 가독성과 속도를 모두 잡았습니다.
import java.util.*;
class Solution {
public int[] solution(int[] numbers, String direction) {
int[] answer = new int[numbers.length];
if (direction.equals("right")) {
System.arraycopy(numbers, 0, answer, 1, numbers.length - 1);
answer[0] = numbers[numbers.length - 1];
} else {
System.arraycopy(numbers, 1, answer, 0, numbers.length - 1);
answer[numbers.length - 1] = numbers[0];
}
return answer;
}
}for 루프를 사용해 일일이 값을 복사하는 대신 JVM의 시스템 수준에서 지원하는 고속 복사 메서드를 사용했습니다. 이를 통해 코드가 훨씬 간결해졌으며 복사 로직이 시스템 최적화되어 더욱 빠르게 동작합니다.
성능 및 메모리는 테스트당 평균 0.01ms를 기록하며 가장 일관된 최상의 성능을 보여주었습니다.
배운점
이번 문제를 통해 자료구조를 무조건적으로 사용하는 것이 항상 좋은 선택은 아님을 깨달았습니다. 상황에 따라 단순히 배열을 직접 조작하는 것이 자료구조 생성보다 메모리 할당을 최소화하고 성능을 극대화하는 데 훨씬 유리할 수 있습니다.
특히 Java의 System.arraycopy 메서드를 사용하면 복잡한 반복문을 코드상에서 제거하여 가독성을 높일 수 있을 뿐만 아니라 시스템 수준의 고속 복사를 통해 실행 효율까지 동시에 확보할 수 있다는 점이 매우 인상적이었습니다. 코딩 테스트 환경에서는 단순히 통과하는 코드보다, 메모리 할당과 복잡도를 세밀하게 조정하여 최적의 성능을 끌어내는 습관을 가지는 것이 무엇보다 중요하다는 점을 다시 한번 깊이 체감했습니다.
