leewwo2o   4년 전

시간초과가 뜹니다 어떤 부분을 바꿔줘야 시간초과가 안뜰까요?

jh05013   4년 전

문제의 설명을 그대로 구현하면 O(N2)이라서 시간초과가 납니다. 아예 새로운 방법을 찾아야 합니다.

leewwo2o   4년 전

배운게 저거 뿐이라서 다른 방법은 모르겠네요 어떤 방식으로 해야 하나요?

jh05013   4년 전

우선 각 노드가 어떤 깊이에 들어가는지 규칙을 찾는 것이 첫 번째 과정입니다.

leewwo2o   4년 전

저렇게 구현하는 것만 배웠고 다른 방법은 아예 모르는데 생각좀 하면 풀수 있을만한 문제 인가요? 

jh05013   4년 전

네. 힌트를 드리자면, 수를 넣을 때마다 각 수가 들어간 깊이를 써 보세요. 예제 입력의 경우 이렇게 나오겠죠.

그리고 std::map을 아신다면 이게 큰 도움이 됩니다.

jh05013   4년 전

사실 꽤 어려운 문제긴 합니다.

leewwo2o   4년 전

아 감사합니다 한번 해볼께요

balupzillot   3년 전

저도 이문제 때문에 계속 헤매고 있는데요

"우선 각 노드가 어떤 깊이에 들어가는지 규칙을 찾는 것" 이 어떤 알고리즘일까요? ㅠ.ㅠ

jh05013   3년 전

제 답변을 이해하지 못하였다는 뜻인가요, 규칙을 모르겠다는 뜻인가요?

balupzillot   3년 전

네, 규칙을 몰라서요ㅠ.ㅠ

말씀하시는 대략적인 알고리즘이, 

"새로운 값을 넣을 때마다 그 값에 해당하는 노드의 깊이를 구해서 N*N 배열에 깊이 값을 저장한다 (새로운 값이 배열의 열의 위치)" <-- 이렇게 이해했구요

이때, 새로운 값을 넣을때 그 값에 해당하는 노드의 깊이를 어떤 규칙으로 찾는건지 감이 안와서요^^


jh05013   3년 전

예제는 규칙을 알아낼 수 있을 만큼 크지 않습니다. N=30 정도의 데이터를 랜덤으로 만들어서 돌려 보면 괜찮을 것 같네요.

한 가지 힌트를 더 드리자면, x를 트리에 넣으면 "x에 가까운 수"의 자식 노드로 들어가게 됩니다.

balupzillot   3년 전

jh0513님이 힌트 주신 방법대로 해봐도 시간 초과네요 ㅠ.ㅠ

jh05013   3년 전

제가 의도한 규칙이 맞다면 그 규칙을 std::map으로 O(nlogn)만에 구현할 수 있습니다. C++ 말고 C에 이게 있는지는 모르겠네요.

balupzillot   3년 전

jh5013님

감사합니다. 덕분에 이진트리를 링크드리스트가 아닌 배열로 짜보는 공부를 잘 했던거 같습니다.

저는 요정도까지만 해도 많이 배운것 같습니다.

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