shfksekdrms2   6년 전

아무리 계산해봐도 O(n) 인거 같은데 도와주세요~ ㅜㅜ

마구 지적해주세요

chogahui05   6년 전

a가 0이고 b가 10만 정도인 Query가 5000개가 들어오면

Query당 O(n)인 코드는 시간초과가 나겠죠?

shfksekdrms2   6년 전

댓글 달아주셔서 감사합니다~

하지만, 다른 분들은 지금 이것과 방법이 똑같은 형식으로 정답으로 떳다고 하는데......

구글링 해도 다 저런 방식으로 풀어 놓은 경우 밖에 안보여서요...

다른 방식으로 어떻게 풀어야 하는지 감이 안오네요... ㅜㅜ

어떤 방식으로 접근하는게 좋을까요? 

shfksekdrms2   6년 전

아래 있는 소스는 통과로 뜨네요...

차이라곤 정렬을 합병정렬(MergeSort)를 사용 했네요

여기서 차이가 많이 나나봐요... 댓글 달아 주셔서 감사합니다.

chogahui05   6년 전

어.. 잘못봤네요. ㅠ

근데 실제로 sh님 코드를 wandbox에서 돌려보니까요. 위에 것은 배열 크기 = 10001로 주고

최악의 TC를 넣어놓았을 때 Q당 0.3-0.5초가 걸린 반면에..


후자는 그렇지 않네요. 이 두 케이스에 대해서 먼저 테스트 해 보심이 좋을 거 같아요. 알고리즘은 저도 함 분석해 볼게요.

shfksekdrms2   6년 전

두 케이스 비교해 보겠습니다~!^^ 도움 주셔서 감사합니다.

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