17298번 - 오큰수
testcase에서 99문제는 통과했는데 나머지 하나가 시간 초과인데... 혹시 어떻게 해결할 수 있을까요??
문제에서 N의 최댓값은 1,000,000 입니다.새로운 노드를 추가할 때, 리스트의 처음부터 끝까지 탐색하고 있습니다.이렇게 되면 입력으로도 O(N2)으로 시간 초과가 납니다.
이것을 해결한다고 하더라고 오큰수 탐색이 O(N2)으로 이 때문에 시간 초과가 다시 발생합니다.이 문제는 완전 탐색으로 풀 수 없는 문제입니다.
stack(스택)을 이용하면 O(N)으로 시간 초과 없이 해결이 가능하므로 stack으로 푸는 것을 추천합니다.
댓글을 작성하려면 로그인해야 합니다.
chschslove 11달 전
testcase에서 99문제는 통과했는데 나머지 하나가 시간 초과인데... 혹시 어떻게 해결할 수 있을까요??