pts119   2년 전

1차원배열로 입력값을 일단 받고 HashMap과 ArrayList을 이용해서 정렬한 결과를 각 단계마다 1차원배열에 넣는 방식으로 풀었습니다.

예를들어 반복문 단계별 디버깅을 하면 HashMap같은경우는 이렇게 나오죠..

{0=[0], 1=[81], 2=[72], 3=[383], 4=[274], 5=[125], 6=[96], 9=[9]}

{0=[0, 9], 2=[125], 7=[72, 274], 8=[81, 383], 9=[96]}

{0=[0, 9, 72, 81, 96], 1=[125], 2=[274], 3=[383]}

쨌든.. 어떤 부분에서 시간을 잡아먹는지 알고 싶은데, 고수님들 도와주세요!!!

chogahui05   2년 전

HashMap에서 극단적으로 충돌이 많이 날 때

시간 복잡도가 O(n)이 아니라 O(nlogn)쯤 될 거 같네요.


그런데. 수의 범위가 1부터 10000까지고, 수의 갯수가 1000만까지 간단 말이죠..

최악의 경우에는 중복되는 키의 갯수가 1000만개 가까이 되네요.


물론, O(nlogn) 복잡도로도 충분히 통과는 가능한데요.

기수 정렬의 특성상 앞에 붙는 상수가 많이 크네요.. 5자리 수인 경우에는 5번 버킷에 넣고 빼고 그래야 하니까요.


아예 버킷과 Arraylist로만 퉁칠 수 있을 거 같은데요. 이 부분은 어떻게 생각하세요??

심지어 이건 수의 범위도 작잖아요.

pts119   2년 전

조언해 주신대로 HashMap을 없애고 ArrayList[] 배열과 ArrayList로 해봤는데 여전히 12%에서 시간초과가떴었구요,

구글링해서 발견한 대상수와 누적수를 이용한 기수정렬로 풀었습니다 ㅎㅎ 이 방법은 1차원 배열만 써먹어서 속도가 개선된거같네요 후우..

쨌든 조언해주신 방법은 참고용으로 아래 소스에 올립니다.

조언 감사드립니다!!!

댓글을 작성하려면 로그인해야 합니다.