ysd1029   2달 전

우선 퀵소트로 시도해보았지만 시간초과가 나서

sort() 메서드를 이용해보았지만 시간초과네요...

어떻게 해야하나요?

ps) Arrays.sort() 는 시간복잡도 몇 정도로 생각하면 될까요?

sksdong1   2달 전

데이터가 퀵소트 최악의 경우로 들어와서 n^2뜨는거 같네요

Arrays.sort()도 퀵소트 정도라고 보시면 될 거에요

이 문제는 주어지는 범위가 -1,000,000~1,000,000 이라는 점을 이용해서

인덱스에 값 자체를 저장하는 방식으로 O(n)에 해결가능해요

ysd1029   2달 전

인덱스에 값자체를 저장하는 방식이란 게 무슨 말인지 궁금합니다 ㅎㅎ

ArrayList로 해서 Collection.sort(arr) 이런식으로 가는걸 말씀하시는건지..음

그리고.. Collection.sort 는 어느정도의 시간 복잡도일까요?

sksdong1   2달 전

문제 조건을 보면 값이 중복되지 않고 범위가 2백만이내이기 때문에

10 50 30 40 5

이런식으로 들어오면 arr[10]=arr[50]=arr[30]=arr[40]=arr[5]=true로 놓고

0부터 true인것만 쫙 출력하면 정렬이 되서 나오겠져

sksdong1   2달 전

컬렉션 소트나 어레이 소트나 같겠죠..

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