문제
https://school.programmers.co.kr/learn/courses/30/lessons/12946
아이디어1
나열을 하면서 패턴을 찾아보자
n = 1 [1 3]n = 2 [1 2] [1 3] [2 3]n = 3 [1 3] [1 2] [3 2] [1 3] [2 1] [2 3] [1 3]n = 4 [1 2] [1 3] [2 3] [1 2] [3 1] [3 2] [1 2] [1 3] [2 3] [2 1] [3 1] [2 3] [1 2] [1 3] [2 3]패턴을 다시 정리해보면
n = 1 [1 3]n = 2 [1 3] [1 2] [2 3]n = 3 [1 3] [1 2] [2 3] [1 3] [3 2] [2 1] [1 3]n = 4 [1 3] [1 2] [2 3] [1 3] [3 2] [2 1] [1 3] [1 2] [2 3] [3 1] [1 2] [2 3] [3 1] [1 2] [2 3]
- 정리된 방식으로 나열하면 중위순회를 통해서 위의 나열 방식으로 다시 바꿀 수 있습니다.
- n이 늘면 leaf 노드가 늘어날 뿐 위의 노드들은 똑같습니다.
[규칙 1] 1, 2, 3 중 없는 숫자가 중앙에 온다 [규칙 2] 왼쪽의 숫자는 왼쪽 자식의 왼쪽 숫자, 오른쪽의 숫자는 오른쪽 자식의 오른쪽 숫자가 된다.
- 1 2 3 중 없는 숫자는 6 - 왼쪽 - 오른쪽을 하면 됩니다.
6 - 1 - 2 = 3 6 - 1 - 3 = 2 6 - 2 - 3 = 1
노드 클래스
template<class T>
void safe_delete(T* ptr)
{
if (ptr != nullptr)
{
delete ptr;
ptr = nullptr;
}
}
class node {
public:
node(int src, int dest, int depth, int max_depth)
: m_vWay{src, dest},
m_iDepth(depth)
{
if (depth < max_depth)
create_child(max_depth);
}
~node() {
safe_delete(left);
safe_delete(right);
}
public:
void inorder_traversal(vector<vector<int>>& arr) {
if (left != nullptr)
left->inorder_traversal(arr);
arr.push_back(m_vWay);
if (right != nullptr)
right->inorder_traversal(arr);
}
private:
void create_child(int max_depth) {
// 1,2면 3 // 1,3이면 2 // 2,3이면 1
int other = 6 - m_vWay[0] - m_vWay[1];
left = new node(m_vWay[0], other, m_iDepth + 1, max_depth);
right = new node(other, m_vWay[1], m_iDepth + 1, max_depth);
}
private:
vector<int> m_vWay;
int m_iDepth = 0;
node* left = nullptr;
node* right = nullptr;
};- 경로 숫자, 깊이, 자식 포인터를 들고 있습니다.
- 생성할 때 최대 깊이가 될 때까지 자식을 만듭니다.
- 중위 순회는 왼쪽 자식, 자신, 오른쪽 자식 순으로 호출합니다.
실행코드
vector<vector<int>> solution(int n) {
vector<vector<int>> answer;
node* head = new node(1, 3, 1, n);
head->inorder_traversal(answer);
delete head;
return answer;
}- 루트 노드는 항상 [1 3]입니다.
마무리
- 짧은 코드들도 많은 거 같은데 내 코드도 이해하기도 가독성도 좋아보이는데 나쁘지 않은 듯?
