ainch96   2년 전

O( n^2 * log n ) 의 풀이로 문제를 풀었습니다만, 시간 초과의 벽에 번번히 막히고 있습니다. 

그 과정에서 map을 사욯했는데, map의 overhead가 워낙 커서 시간 초과가 뜨는지, 아니면 애초에 이 시간 복잡도로 풀 수 없는 문제인지 잘 모르겠습니다. 

n=1000이라 충분했다고 생각했지만 생각해보니 테스트 케이스가 여러개라서... 그런가 싶기도 하고요.

혹시 이 문제를 O(n^2) 으로 풀 수 있는 방법이 존재하는 건가요? 

혹시 이 문제를 O(n^2)으로 푸신 분이 있다면, O(n^2)으로 풀 수 있다고 알려주시면 감사하겠습니다. 


만약 이 질문이 문제시 되어 삭제해야 한다면 삭제하겠습니다.

sgchoi5   2년 전

Waterloo 문제는 정답 코드가 있거든요.. 한 번 분석해 보시는 것도..

http://gooddaytocode.blogspot....

irishw   2년 전

O(N^2) 정도로 풀리네요. 

그리고pinch3773코드 봤습니다.

출력할때 끝에 "\n"추가 하셔야 할듯 ^^...(저도 빼먹어서;;;;;)


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