jyunni   2년 전

List를 생성해서 lower bound를 하고 insert를 해도 시간초과가 발생합니다.
그리고 C#에는 자바처럼 treeset이 없습니다.

구글링을 해서 다른분들의 풀이를 참고해도 틀리는데 제한시간을 늘릴 필요가 있다고 생각합니다.

sdpr   2년 전

27232같은 문제도 BBST(트리맵)을 사용하는게 정해이지만, 에디토리얼에서조차 BBST가 없는 언어 사용 시 BBST를 직접 구현하거나 아예 세그먼트트리, 제곱근 분할법 등의 난이도보다 훨씬 높은 수준의 자료구조/알고리즘을 사용하라고 합니다. 이 문제의 경우, 정말 풀 방법이 BBST밖에 답이 없다면 직접 구현하셔야 할 것 같네요. C++, 자바등에서 BBST를 구현할 때 사용하는 레드블랙트리를 검색해보시길 바랍니다.

이외에도 난이도가 올라갈수록 C++/Rust등의 매우 빠른 속도를 자랑하는 언어가 아니면 아예 풀 수 없는 문제도 많아집니다. 이건 사용 언어로 C#을 선택하신 jyunni님에게 어쩔 수 없이 주어지는 책임입니다.

당장에 저도 Ruby와 같이 속도에 비해 추가시간이 부족한 언어를 사용합니다. (어느수준이냐면, 인터프리터언어주제에 컴파일언어인 C#/자바/코틀린과 같은 추가시간을 가집니다.) 이 때 시간복잡도를 아무리봐도 시간초과가 나지 않을 경우 Go, Rust등의 빠른 언어를 사용합니다.

그리고 List에 lowerbound 후insert하는건 logN + N으로 시간초과가 나는게 당연합니다. BBST는 삽입에 logN이니까요.

jyunni   2년 전

힌트 주셔서 감사합니다, 제가 잘못풀고 있었네요... 덕분에 C++로 풀었습니다.

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