이런방법이 있다니 너무 신기합니다!
하나 궁금한게 있어 질문드립니다.
혹시 이 방법으로 5 4 5 4 6 7 이 주어지고, 5(인덱스가 2인)의 오큰수를 구하고싶다고 치면
5 4 5 4 6 7 -1 -1 의 형태로 위처럼 이진트리를 만들고 왼쪽 서브트리는 제외하고 오른쪽 서브트리만 생각할텐데
이때, 오른쪽서브트리 6,7에서 7의 값이 부모노드로 되어있어 단순히 7을 정답으로 하면 오답이 날겁니다. 그러면 결국 자식노드까지 다 비교를 해봐야할텐데, 위의 예시에도 결국 4 5중에 4를 고른다음에 4의 자식노드들도 확인을 하는건가요?
paraworld 3년 전 1
NlogN이라 생각하는데, 시간초과가 나네요. 이 문제에 이진트리 사용하면 시간 초과인지, 아니면 이진 트리가 잘못 구현된 건지 모르겠습니다.
로직은 아래와 같습니다.
5
5 4 3 4 5 라고 할 떄, 이런 식의 트리가 나오게 했습니다. null값은 -1로 박아 넣었습니다.
각 노드의 값은 자식 노드들 중 가장 큰 수의 값입니다.
트리를 잘못 구현한걸 확인하고 고치니까 맞았습니다.
이때 3의 오큰수를 구한다면
위쪽 노드 두개 다 3 이후에 등장하는 3보다 큰 수를 가지니 둘다 접근합니다.
(코드 96, 98번째줄 조건)
여기서 왼쪽의 노드의 자식 둘중 x표시한 5의 자식 노드들은 3보다 이전에 나오니 오큰수가 될 수 없으니 패스하고, 4만 넣습니다.
오른쪽의 자식 노드 둘중 x표시한 -1은 3보다 작은 수이니 패스합니다.
여기서 한번 더 진행하면 4, 5 두개의 값이 나오는데, 이때 4가 5보다 먼저 나오니 여기서의 오큰수는 4가 나오는 식입니다. (103번줄)