ykwon3357   2년 전

input                  output
1
1 -1 -1
1 1

3
2 3 -1
1 2 -1
3 -1 -1
1 1

5
5 -1 -1
1 -1 4
4 -1 -1
2 1 3
3 5 -1
2 5

5
5 -1 -1
1 4 5
4 -1 -1
2 1 3
3 -1 -1
2 4

5
5 -1 -1
1 2 3
2 4 -1
3 -1 5
4 -1 -1
3 5

5
2 1 3
1 4 -1
4 -1 -1
3 5 -1
5 -1 -1
2 4

5
3 -1 5
2 1 3
1 -1 4
4 -1 -1
5 -1 -1
2 4

5
4 -1 -1
2 1 3
1 -1 -1
3 4 5
5 -1 -1
2 4

8
1 2 3
2 4 -1
3 8 -1
4 -1 5
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1
3 7

6
1 2 3
2 5 4
3 -1 6
4 -1 -1
5 -1 -1
6 -1 -1
3 6

root가 1이 아닌 경우,

노드의 번호가 1 ~ N 순서대로 입력되지 않을경우 등 고려하여

위와 같은 테스트케이스들 만들어서 해봤는데 다 문제 없습니다.

자꾸 3프로에서 틀렸다고 나오는데 뭐가 문제일까요..? 하루종일 붙잡고있네요 제발 도와주십시오ㅠㅠ

++

아래 댓글로 알려주신 테스트케이스 반영해서 

너비를 data배열의 순서로 구하는게 아닌, 최댓값 - 최솟값 +1 로 구해서 3프로의 벽은 넘었습니다. 감사합니다!!

그런데 이제는 20몇프로에서 틀렸습니다가 뜨네요.. 도대체 또 뭐가 문제일까요..

다시 고민해봤는데 도저히 모르겠네요..다시한번 부탁드리겠습니다ㅠㅠ

f52985   2년 전

Python 3.7 이상이라면, 다음과 같은 입력에서 문제가 확정적으로 생깁니다.

6
1 2 3
2 5 4
3 -1 6
4 -1 -1
5 -1 -1
6 -1 -1

정답: 3 6

출력: 2 4

핵심은 46번째 줄로, order에 담긴 인덱스가, 한 행에서 좌->우의 순서로 정렬이 되어있지 않을 수 있다는 점입니다.

이는 tree.keys()가 (python 3.7 기준으로) 입력이 들어온 순서대로 keys를 리턴하고, sorted는 stable sort이기 때문입니다.

위의 예제에서는 5가 4보다 위치적으로 왼쪽에 존재하지만, 입력은 4, 5의 순서로 주었기 때문에,

sorted에는 [1,2,3,5,4,6]이 아닌 [1,2,3,4,5,6]의 순서로 저장이 될 것입니다.

ykwon3357   2년 전

@f52985

댓글로 알려주신 테스트케이스 반영해서

너비를 data배열의 순서로 구하는게 아닌, 최댓값 - 최솟값 +1 로 구해서 3프로의 벽을 드디어 넘었습니다!

정말 감사합니다!!

그런데 이제는 20몇프로에서 틀렸습니다가 뜨네요.. 도대체 또 뭐가 문제일까요..

다시 고민해봤는데 도저히 모르겠네요..다시한번 부탁드리겠습니다ㅠㅠ

ykwon3357   2년 전

42번째줄 root = int(math.log(root, 2)) 이게 문제였습니다..

파이썬 math모듈이 오차가 좀 있어서 4.9999999 5.000001 이런경우가 있기에..

이 코드 그대로 pypy로 제출하면 통과,

python으로 제출할경우 로그결과값에 0.5 더해주는 식으로 통과 int(math.log(root, 2)+0.5)

dh0450   2년 전

루트가 1 고정이 아니었다니 ㄷㄷ

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