문제 설명
당신은 이진트리를 수로 표현하는 것을 좋아합니다.
이진트리를 수로 표현하는 방법은 다음과 같습니다.
- 이진수를 저장할 빈 문자열을 생성합니다.
- 주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
- 만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
- 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
- 문자열에 저장된 이진수를 십진수로 변환합니다.
이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.
다음은 이진트리를 수로 표현하는 예시입니다.
주어진 이진트리는 다음과 같습니다.
주어진 이진트리에 더미노드를 추가하여 포화 이진트리로 만들면 다음과 같습니다. 더미 노드는 점선으로 표시하였고, 노드 안의 수는 살펴보는 순서를 의미합니다.
노드들을 왼쪽에 있는 순서대로 살펴보며 0과 1을 생성한 문자열에 추가하면 "0111010"이 됩니다. 이 이진수를 십진수로 변환하면 58입니다.
당신은 수가 주어졌을때, 하나의 이진트리로 해당 수를 표현할 수 있는지 알고 싶습니다.
이진트리로 만들고 싶은 수를 담은 1차원 정수 배열 numbers가 주어집니다. numbers에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ numbers의 길이 ≤ 10,000
- 1 ≤ numbers의 원소 ≤ 10^15
숫자 n을 2진수로 표현할 때 k bit 가 필요하다.
포화 이진트리의 노드 개수는 2^n - 1 (이하 len으로 칭함) 개다.
k < len인 len을 구한다음 숫자 n 을 len의 길이의 이진수로 만든다.
이 이진수의 각 비트를 노드라고 생각했을 때 len개의 노드가 있다.
시작(s)~끝(e) 범위 노드를 확인할 때 루트 노드( (s + e) / 2)부터 확인해 나가는 데
- 확인하는 노드가 0이라면 해당 노드 아래에는 더미 노드만 존재해야 표현가능한 이진트리이다.
- 노드가 1이라면 자식 노드를 확인해야 한다.
맞게 푼 것 같은데 seg fault 가 나왔다. 배열은 bin 밖에 선언하지 않았는데 seg가 나서 이상했다. if/else 문을 주석처리하니 나지 않아서 해당 함수 문제있은 줄 알았다. 하지만 len의 최댓값이 이론상 63인데 왜 에러가 나는지 모르겠어서 check(0, len)만 따로 빼서 확인했다. c이때는 에러가 나지 않았다. 그렇다면 push_back에서 에러가 난다는 말인데 뭔가 이상했다. 그래서 혹시나 싶어 루프별로 bin을 memset 해주니 에러가 나지 않았다. push_back에서 난 에러를 memset(bin)을 통해 해결한 게 무척이나 이상했다. 아마 solution 함수를 호출하는 Main에서 무언가 일어나는 것일까? 이제 seg 가 날 때는 배열 인덱스 말고 초기화도 생각해 보아야겠다.
'코딩 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 숫자 카드 나누기 - C++ (0) | 2023.04.06 |
|---|---|
| [프로그래머스] 점 찍기 - C++ (0) | 2023.04.03 |
| [프로그래머스] 귤 고르기 - C++ (0) | 2023.03.30 |
| [프로그래머스] 미로 탈출 명령어 (0) | 2023.03.29 |
| [프로그래머스] 디펜스 게임 - C++ (0) | 2023.03.28 |