알고리즘 문제를 풀 때 가독성과 성능 사이에서 고민하는 것은 모든 개발자의 숙제인 것 같다. 최근 같은 숫자는 싫어 문제를 풀며 어떤 도구를 선택하느냐에 따라 성능이 얼마나 드라마틱하게 변하는지를 체감했다. 나의 풀이 과정을 통해 그 고민과 결론을 공유해 본다.
첫 번째 시도: Stack을 이용한 직관적인 풀이
처음에는 문제의 핵심이 '연속된 중복 제거'라는 점에 집중하여 Stack을 떠올렸다. 마지막에 들어온 값과 현재 값을 비교하기에 peek()만큼 적합한 도구는 없었기 때문이다.
Stack<Integer> stack = new Stack<>();
for(int i : arr) {
if (!stack.isEmpty() && stack.peek() == i) continue;
stack.push(i);
}
int[] answer = new int[stack.size()];
int idx = stack.size() - 1;
while (!stack.isEmpty()) {
answer[idx--] = stack.pop();
}
return answer;Stack 클래스를 사용하여 로직을 매우 직관적으로 구현할 수 있었다. 하지만 Stack은 내부적으로 Vector를 상속받아 동기화(synchronized) 처리가 되어 있어 단일 스레드 환경인 알고리즘 풀이에서는 불필요한 오버헤드가 발생한다는 점이 조금 아쉬웠다.
두 번째 시도: 가독성을 높인 ArrayList와 Stream
코드의 가독성을 더 좋게 만들 수는 없을까 고민하며 ArrayList와 Stream API를 사용해 보았다.
ArrayList<Integer> list = new ArrayList<>();
int prev = -1;
for (int i : arr) {
if (list.isEmpty() || prev != i) {
list.add(i);
prev = i;
}
}
return list.stream().mapToInt(i -> i).toArray();이 방식은 코드가 매우 간결해지고 현대적인 Java 스타일로 작성되어 유지보수 측면에서 매우 훌륭해 보였다. 하지만 테스트를 진행하자 성능 면에서 아쉬움이 남았다. 정확성 테스트에서는 통과했지만 효율성 테스트에서 앞선 풀이보다 시간과 메모리 사용량이 늘어난 것을 확인했다. 여기서 '코드의 간결함 뒤에 숨겨진 비용'이 무엇인지 깊이 있게 파고들어 보기로 했다.
성능 최적화를 위한 원인 분석
결과적으로 배열을 직접 활용하는 방식으로 최적화를 시도했고, 그 결과 속도가 0.01ms대까지 비약적으로 상승했다. 성능 차이가 발생한 핵심 이유는 크게 세 가지였다.
-
오토박싱(Autoboxing) 비용:
ArrayList<Integer>는 원시 타입인int를Integer객체로 변환하여 저장한다. 이 과정에서 힙 메모리에 객체를 생성하고 처리하는 비용이 발생하는데 대량의 데이터를 다룰 때 이 오버헤드는 무시할 수 없는 수준이다. -
컬렉션 프레임워크의 오버헤드:
ArrayList는 내부적으로 용량이 부족해질 때마다 더 큰 배열을 새로 생성하고 기존 데이터를 복사하는 '리사이징(Resize)' 과정을 거친다. 데이터가 많아질수록 이러한 내부 동작은 성능 저하의 주범이 된다. -
Stream API의 추상화 비용:
Stream은 가독성 면에서는 최고지만 내부적으로 스트림 파이프라인 생성, 반복자 처리, 언박싱 과정이 포함되어 있다. 단순한 반복문(for-loop)보다 CPU 사이클을 더 많이 소모하게 된다.
최종 결론: 배열 직접 활용으로 성능 최적화
결국 성능 최적화를 위해 객체 생성을 최소화하고 원시 타입 배열을 직접 제어하는 방식으로 코드를 개선했다.
int[] temp = new int[arr.length];
int count = 0;
for (int i = 0; i < arr.length; i++) {
if (i == 0 || arr[i] != arr[i - 1]) {
temp[count++] = arr[i];
}
}
int[] answer = new int[count];
System.arraycopy(temp, 0, answer, 0, count);
return answer;이 방식은 메모리를 미리 할당해 두고 인덱스 포인터(count)만 관리하기 때문에 JVM이 가장 최적화하기 좋은 형태가 된다.
결과적으로 이번 학습을 통해 "가독성을 위해 Stream을 선택할지, 극한의 성능을 위해 원시 배열을 선택할지"에 대한 명확한 기준을 세울 수 있었다. 실무에서는 유지보수를 고려해 가독성을 우선시하겠지만 대규모 데이터를 처리하거나 성능이 중요한 알고리즘 문제에서는 당연히 원시 타입 중심의 최적화된 로직을 선택해야 한다는 것을 깨달았다. 이제는 상황에 맞춰 최적의 도구를 꺼내 쓰는 능력을 갖추게 된 것 같아 뿌듯하다.
