문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.
예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
제한사항
배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
처음 풀었던 풀이
public static int[] jisooSolution(int[] arr) {
Stack<Integer> stack = new Stack<>();
stack.push(arr[0]);
for (int i = 1; i < arr.length; i++) {
if (!stack.peek().equals(arr[i])) {
stack.push(arr[i]);
}
}
int[] answer = new int[stack.size()];
for (int i = 0; i < stack.size(); i++) {
answer[i] = stack.get(i);
}
return answer;
}
정확성 테스트
최소 시간: 0.12ms (테스트 1)
최대 시간: 0.31ms (테스트 15)
효율성 테스트
최소 시간: 46.60ms (테스트 1)
최대 시간: 80.48ms (테스트 4)
다른 사람의 풀이
public static int[] solutionUsingArrayList(int[] arr) {
ArrayList<Integer> tempList = new ArrayList<>();
int preNum = 10;
for (int num : arr) {
if (preNum != num)
tempList.add(num);
preNum = num;
}
int[] answer = new int[tempList.size()];
for (int i = 0; i < answer.length; i++) {
answer[i] = tempList.get(i).intValue();
}
return answer;
}
정확성 테스트
최소 시간: 0.03ms (테스트 12)
최대 시간: 0.22ms (테스트 2)
효율성 테스트
최소 시간: 22.87ms (테스트 2)
최대 시간: 27.60ms (테스트 4)
정확성 테스트 뿐 아니라 효율성 테스트에서도 시간이 확 줄어든 것을 볼 수 있다. 내가 봤을 때는 Stack을 이용하여 문제를 푸는 것이 훨씬 빠르다고 생각했는데, 이상하다고 생각하여 GPT에게 성능을 비교할 수 있는 코드를 부탁하여 보았다.
메서드 성능 직접 비교
public class TestOfCode {
public static void main(String[] args) {
// 랜덤으로 배열을 생성하는 메서드
int[] arr = generateRandomArray(10_000_000);
// 첫 풀이 : 690ms
long start1 = System.currentTimeMillis();
int[] result1 = jisooSolution(arr);
long end1 = System.currentTimeMillis();
System.out.println("처음 풀이 : " + (end1 - start1) + "ms");
// arraylist를 이용한 다른사람의 풀이 : 346ms
long start2 = System.currentTimeMillis();
int[] result2 = solutionUsingArrayList(arr);
long end2 = System.currentTimeMillis();
System.out.println("다른 사람의 풀이(arraylist 이용) : " + (end2 - start2) + "ms");
}
// 처음에 내가 풀었던 풀이
public static int[] jisooSolution(int[] arr) {...}
// arraylist를 이용한 다른 사람의 풀이
public static int[] solutionUsingArrayList(int[] arr) {...}
// 성능 테스트를 위해 랜덤으로 백만개의 0~9의 원소를 가진 배열 생성 -> gpt가 만들어줌!
// random.nextInt(n) 메서드는 0이상 n미만의 범위에서 랜덤으로 정수를 생성하는 메서드.
public static int[] generateRandomArray(int size) {
int[] arr = new int[size];
Random random = new Random();
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(10);
}
return arr;
}
}
랜덤배열을 생성하여 성능 시험을 해보아도 거의 시간이 반정도 차이가 남을 알 수 있다.
(Random.nextInt(n) 메서드는 처음 보았다! 가볍게 성능 테스트할 때는 이런 식으로 하면 되겠구나!를 알게 됨.)
stack에서 배열로 바꿔 줄 때, pop()으로 바꿔 준 후 index를 거꾸로 넣어주면 좀 더 빠르겠구나 싶어 다시 돌려 보았다.
pop() 사용하고, 다시 테스트해보기
public static int[] jisooSolution(int[] arr) {
Stack<Integer> stack = new Stack<>();
stack.push(arr[0]);
for (int i = 1; i < arr.length; i++) {
if (!stack.peek().equals(arr[i])) {
stack.push(arr[i]);
}
}
int[] answer = new int[stack.size()];
for (int i = stack.size() - 1; i >= 0; i--) {
answer[i] = stack.pop();
}
return answer;
}
처음 풀이 : 547ms
다른 사람의 풀이(arraylist 이용) : 305ms
정확성 테스트
최소 시간: 0.11ms (테스트 17)
최대 시간: 0.38ms (테스트 9)
효율성 테스트
최소 시간: 48.72ms (테스트 3)
최대 시간: 53.33ms (테스트 2)
아까 보다는 줄어든 것 같긴 하지만 그래도 ArrayList보다는 확연히 느린 것 같다.
왜 ArrayList를 이용한 풀이가 Stack을 이용한 풀이보다 더 빠를까?
자료 구조에 대해 공부가 부족해서 GPT에게 코드 두 개를 던져주며 왜 내 풀이가 더 느린건지 물어 보았다. 그에 대한 답변을 정리해 놓는다.
Stack의 오버헤드
Stack은 데이터를 삽입 및 삭제하는 과정에서 발생하는 오버헤드로 인해 실행 시간이 증가할 수 있다. 여기서 오버 헤드란 어떤 작업을 수행할 때 추가적으로 발생하는 부가적인 비용 또는 부담을 의미한다. 스택을 삽입 및 삭제하는 과정에서 발생하는 오버헤드는 다음과 같은 작업을 포함한다.
- 메모리 할당 : 새로운 요소를 스택에 삽입할 때, 해당 요소를 저장할 메모리 공간을 할당해야 한다. 이는 동적으로 메모리를 할당하는 작업이므로 일정한 시간이 소요된다.
- 포인터 조작 : 스택의 peek()를 가리키는 포인터를 업데이트해야 한다. 요소를 삽입할 때에는 포인터가 새로운 요소를 가리키도록 업데이트되고, 요소를 삭제할 때는 포인터가 이전 요소를 가리키도록 업데이트해야 한다. 이러한 포인터 조작은 추가 연산을 필요로 하며, 실행 시간에 영향을 줄 수 있다.
- 메모리 해제 : 스택에서 요소를 삭제하면 해당 요소의 메모리를 해제해야 한다. 메모리 해제는 삭제된 요소가 더 이상 필요하지 않을 때 수행되는 작업으로, 해당 메모리 공간을 다른 용도로 활용할 수 있도록 한다. 메모리 해제 작업도 역시 일정한 시간이 소요된다.
이러한 삽입 및 삭제 과정에서 발생하는 오버헤드는 스택의 크기에 따라 증가할 수 있다. 특히 큰 크기의 스택을 사용하거나 반복적으로 삽입 및 삭제 작업을 수행할 때는 오버헤드가 더 크게 나타날 수 있다. 따라서 스택을 사용하는 경우에는 이런 오버헤드를 고려하여 실행 시간이 증가할 수 있음을 유념해야 한다.
ArrayList의 오버헤드
ArrayList를 이용한 풀이의 경우 추가와 조회 메서드만 사용하였는데, 물론 이 때도, 오버헤드가 발생할 수는 있으나, 성능상의 문제로 이어지지는 않는다. 데이터 추가와 조회에 대한 주요 오버헤드는 다음과 같다.
데이터 추가
- 용량 증가 : ArrayList는 크기를 동적으로 조절하기 위해 내부 배열의 용량(capacity)을 관리한다. 삽입 작업에서 용량이 부족한 경우는 내부 배열의 크기를 확장해야 한다. 이 때 용량 증가에 따른 재할당 작업이 필요하며, 데이터 복사 등의 추가 작업이 수반될 수 있다.
- 인덱스 이동 : 삽입 작업은 특정 인덱스에 요소를 삽입하는 경우가 있다. 이 경우 해당 인덱스 이후의 요소들을 모두 한칸씩 뒤로 이동시켜야 한다. 이는 데이터의 이동 작업으로서 오버헤드가 발생할 수 있다.
데이터 조회
- 인덱스 계산 : ArrayList는 인덱스를 기반으로 데이터에 접근한다. 따라서 원하는 위치의 인덱스를 계산하는 작업이 필요하다. 이는 인덱스 계산에 따른 오버헤드가 발생할 수 있지만, 일반적으로 미세한 차이로 인해 성능에 큰 영향을 주지 않는다.
- 배열의 접근 : ArrayList는 내부 배열을 사용하여 데이터를 저장한다. 따라서 데이터를 조회할 때는 내부 배열을 통해 접근해야 한다. 이는 배열 접근에 따른 오버헤드가 발생할 수 있으며, 하드웨어의 캐시 효율성과 관련하여 성능에 영향을 줄 수 있다.
ArrayList의 장점인 동적 크기 조절과 빠른 인덱스 기반 조회를 고려할 때, 일반적으로 발생하는 오버헤드는 사용상의 이점에 비해 미비하다.
이런 원인들에 의해서 내 풀이보다 ArrayList를 이용한 풀이가 더 효율적인 코드임을 알 수 있다!
나는 이제껏 GPT에 대해서 부정적인 시선을 가지고 있었는데, 이번의 경우에는 빠르게 내가 원하는 것을 알아 낼 수 있어서 좋았던 것 같다. 나중에 이 기록을 보고 직접 ArrayList와 Stack의 구현 방법에 대해서 공부해보고 다시 기록을 남겨 놓아야겠다.
'STUDY > JAVA' 카테고리의 다른 글
[TIL] 프로그래머스 - 상담원 인원(첫 lv.3 도전) (0) | 2023.07.31 |
---|---|
[TIL] java.lang.IllegalStateException 해결하기 (0) | 2023.06.26 |
[TIL] 피보나치 수열 구하기 - 메모이제이션 (0) | 2023.06.23 |
[TIL] 프로그래머스 lv.2 다음 큰 숫자 (비트연산자) (0) | 2023.06.22 |
[TIL] 예외 되던지기(Exception re-throwing)는 언제 사용될까? (0) | 2023.06.21 |