https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14w-rKAHACFAYD&categoryId=AV14w-rKAHACFAYD&categoryType=CODE&problemTitle=1228&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

해당 문제를 풀다가 문제의 정답은 배열에서 앞의 10개만 출력하면 된다 생각해서 리스트를 안쓰고 배열로 풀이했다.

리스트로 입력값들을 모두 중간 삽입하여 풀이할 수도 있지만 효율이 떨어진다고 판단했다.

하지만 문제의 경우 n의 크기가 작기때문에 유의미한 차이를 얻을 수 없었고 이를 검증하기 위해 n이 10만인 예시를 통해 시간을 측정해보았다.

Test 1

62590900

Test 2

72999900

Test 3

78784200

---

테스트 결과

Test 1은 배열에서 출력해야하는 10개만 남기고 그 이상으로 index가 출발할 경우 무시

Test 2은 링크드리스트로 구현. index 부터 모든 추가해야하는 값 추가

Test 3은 어레이리스트로 구현. 나머지는 2와 동일

2 vs 3

2와 3이 차이가 난 이유는 링크드 리스트와 어레이 리스트의 차이에서 발생.

중간 삽입을 할 경우 링드트 리스트는 위치를 찾는데 O(n), 삽입에 O(1).

반면 어레이 리스트는 위치를 찾는데 O(1), 삽입에 O(n).

얼핏보면 차이가 없어 보이지만 어레이 리스트의 중간 삽입에는 memory copy가 발생!! 이로 인한 차이로 추정

1 vs other

n이 충분히 작고 삽입할 위치가 충분히 앞이라면 비슷한 성능을 낼 수 있을것이라 기대.

하지만 1의 방법은 앞에서 10개만 보는 휴리스틱을 적용했기때문에 더 나은 성능을 낼 수 있을 것이라 기대됨

번외

Deep Copy vs Narrow Copy

깊은 복사와 얕은 복사

자바의 경우 call by reference를 사용하기 때문에 모든 객체는 참조 변수로 존재한다(힙 영역에 존재).

int[] s1 = new int[3];
s1 = {1,2,3};
int[] s2 = s1;

s1[2] = 4;

print(s2); // 1,2,4 출력

위와 같은 방법을 얕은 복사라 한다.

s2가 참조하는 힙 영역은 s1이 참조하는 영역과 같기때문에 s1의 값을 변경시켜주면 s2도 자연스럽게 변경된다.

s2를 s1과 별개의 객체로 다루고 싶을 때 이는 문제가 된다. 그래서 자바에서도 깊은 복사를 지원한다.

int[] s1 = new int[3];
s1 = {1,2,3};
int[] s2 = Arrays.copyOf(s1, s1.length);

s1[2] = 4;

print(s2); // 1,2,3 출력

s2는 변경없이 값이 유지되는 것을 확인할 수 있다.

난수발생기

http://mwultong.blogspot.com/2008/01/random-int-number-generator.html