nayounsang1   1년 전

혹시 의도한걸까요? O(N)풀이가 가능한걸까요?

풀이 내부적으로 sort를 사용했으며

경험상 dict사용시 상수가 매우 커 N개 만큼 생성시 O(NlogN), 읽기시 O(logN) 과 비슷하긴 합니다.

jun83   1년 전

코드를 올려주셔야 어느 부분에서 문제가 발생했는지 알 수 있습니다.

추가로 "추가 시간 없음" 문제이기 때문에 같은 로직으로 짜더라도 일부 언어는 AC를 받을 수 없을 수도 있습니다.

jiminp   1년 전

  1. 네, O(N) 풀이가 가능합니다.
  2. sort 필요하지 않습니다.
  3. "추가 시간 없음"이지만 파이썬으로 100ms 풀이가 가능합니다.

import gc; gc.disable() 하고 코드 제출해보니 "틀렸습니다"가 뜨네요...

알고리즘을 그대로 사용한다고 해도 코드에 최적화 할 여지가 많아 보입니다. 예를 들어 sorted_to_original는 sorted(range(N), key=A.__getitem__)과 같이 구할 수 있습니다.

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