코딩테스트와 실무 역량 모두잡는 알고리즘 스터디(JAVA)
시간복잡도 계산하기
‘완주하지 못한 선수’는 사실 ArrayList를 사용해서도 풀 수 있지만, 효율성 테스트에서 실패한다.
HashMap을 사용하여 O(n)으로 시간복잡도를 낮춰야 효율성이 개선된다.
그 이유는, 시간복잡도를 계산해보면 알 수 있다.
기본적으로 Arrays.sort()로 정렬을 한다는 자체가, 사실 한 번의 반복문을 돌아서 가장 효율적이라고 알려진 quick sort나 merge sort여도 O(nlogn)의 복잡도가 나오게 되기 때문이다.
엔지니어처럼 생각하기
- 우리는 사이언티스트가 아니라 엔지니어니까 경제적으로 생각해야 한다.
- 만약 O(n^2)보다 빠르기만 하면 된다는 요구사항을 받았을 경우, O(nlogn) -> O(n)으로 개선하는데 시간이 배로 더 걸린다면, 굳이 그렇지 않아도 된다.
