a가 0이고 b가 10만 정도인 Query가 5000개가 들어오면
Query당 O(n)인 코드는 시간초과가 나겠죠?
7469번 - K번째 수
a가 0이고 b가 10만 정도인 Query가 5000개가 들어오면
Query당 O(n)인 코드는 시간초과가 나겠죠?
댓글 달아주셔서 감사합니다~
하지만, 다른 분들은 지금 이것과 방법이 똑같은 형식으로 정답으로 떳다고 하는데......
구글링 해도 다 저런 방식으로 풀어 놓은 경우 밖에 안보여서요...
다른 방식으로 어떻게 풀어야 하는지 감이 안오네요... ㅜㅜ
어떤 방식으로 접근하는게 좋을까요?
아래 있는 소스는 통과로 뜨네요...
차이라곤 정렬을 합병정렬(MergeSort)를 사용 했네요
여기서 차이가 많이 나나봐요... 댓글 달아 주셔서 감사합니다.
어.. 잘못봤네요. ㅠ
근데 실제로 sh님 코드를 wandbox에서 돌려보니까요. 위에 것은 배열 크기 = 10001로 주고
최악의 TC를 넣어놓았을 때 Q당 0.3-0.5초가 걸린 반면에..
후자는 그렇지 않네요. 이 두 케이스에 대해서 먼저 테스트 해 보심이 좋을 거 같아요. 알고리즘은 저도 함 분석해 볼게요.
두 케이스 비교해 보겠습니다~!^^ 도움 주셔서 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
shfksekdrms2 6년 전
아무리 계산해봐도 O(n) 인거 같은데 도와주세요~ ㅜㅜ
마구 지적해주세요