요즘 Do it 알고리즘 코딩테스트 - 자바편이란 책으로 알고리즘 공부를 하고있다.
책의 슬라이딩 윈도우 챕터에 나오는 백준 11003번 문제 - 최소값 찾기를 풀이대로 푸는데 문제가 발생했다.
문제
정확한 코드는 책의 내용이니 공개하지 못하지만 대충 말하면
- 시간복잡도를 위해 정렬 과정을 생략
- Deque를 이용해 index와 value를 가진 Node class를 담음
- 입력받은 값과 Deque의 last 요소의 값을 비교하며 입력받은 값보다 작은 요소를 제거하는 방식으로 정렬 효과(시간복잡도를 위해)
이런 로직이었는데, Java코드로 동일한 코드를 제출하면 문제없이 통과가 됐다.
하지만 Kotlin으로 제출하면 테스트 케이스를 얼마 돌리지도 않고 시간초과가 터졌다.
시간을 줄일 수 있는 부분은 최대한 줄였다고 생각해 유튜브 개발바닥 채널에서 운영하는 개발바닥 단톡방에 질문을 올렸다.
질문을 올리고 11시 30분까지 머리를 싸매다가 출근을 위해 잘준비를 했는데, 그사이에 다른 답변을 주신 분이 계셨다.
해결
기존 구현 코드는 Deque의 구현체로 LinkedList를 사용했는데, ArrayDeque를 써보니 간당간당하게 통과했다는 답변을 달아주셨다.
그래서 아침에 일어나자마자 변경하고 돌려보았다.
통과는 했지만, 첫번째 시도는 시간초과가 났고 동일 코드로 재시도를 했더니 통과가 됐다.(이 부분에서 나의 실수가 하나 있었다)
LinkedList vs ArrayDeque
ArrayDeque와 LinkedList 간에 어떤 차이가 있길래 이런 결과가 나왔나 너무 궁금했다.
LinkedList는 순서를 보장해주는 List의 구현체라고 알고있었고, 일단 간단히 ArrayDeque에 대해 찾아보려 했다.
그런데 너무나도 감사한 우테코.... 우테코 3기 수료생 중 와일더님께서 작성해주신 블로그가 있었다.
LinkedList와 ArrayDeque에 대해 비교해주신 글이었고, 완전 깊은 내용은 아니지만 어떤 차이가 있는지는 충분히 알 수 있는 글이었다.
평소 다른 블로그를 그대로 옮겨적은듯한 내용의 글을 싫어해서... 그냥 해당 블로그를 캡쳐해왔다(이미지를 클릭해도 해당 블로그로 이동합니다)
추가적인 내용으로는
- Queue가 필요한 경우 Deque를 사용해라
- 대부분의 상황에선 구현체로는 LinkedList 보단 ArrayDeque를 사용해라
라는 내용이었다.
하지만 난 다른 문제를 맞이했는데...
Kotlin에서의 ArrayDeque
기존 Deque의 구현체로 LinkedList() 를 선언한 변수를 ArrayDeque() 로 변경했더니 type 에러가 발생했다.
그래서 자료형을 ArrayDeque로 변경하고 문제를 제출해 처음에 시간초과가 났었다.
찾아보니 Kotlin에서 MutableList의 구현체로 만든 kotlin.collections.ArrayDeque가 따로 존재했던 것이다.
제공되는 함수나 대부분 비슷한 기능인거 같은데 Deque의 구현체가 아닌 List의 구현체인 이유는 더 찾아봐야 할듯 하다
어쨌든 java.util.ArrayDeque로 변경하고 나서 제출했더니, 메모리도 적고 시간도 100ms 감소하는 결과가 나왔다!
위에서 부터
java.util.ArrayDeque
kotlin.collections.ArrayDeque
kotlin.collections.LinkedList
순이다.
자료구조는 참 어렵고도 재밌는거 같은데 공부할게 아직 많다는게 큰 문제다.....ㅠㅠㅠ
