실패로 얼룩진 이진트리 탐색 220417

1. 이진트리 탐색을 순차 탐색으로 변경

https://leetcode.com/problems/increasing-order-search-tree/

Increasing Order Search Tree - LeetCode

소감

이진 탐색 트리를 어떻게 조회하는지 모르겠다. 문제의 해답을 1시간 30분 고민 끝에 봤는데,
자바와 파이썬으로 이루어진 코드여서 그냥 닫았다. 댓글 중에 "이건 미디엄 난이도라고 생각한다"는 글이 눈에 띈다.

겪은 어려운 점

이진 탐색 트리는 구조가 

1. 자신의 값
2. 왼쪽 노드
3. 오른쪽 노드

로 이루어져 있다.  자신의 값은 왼쪽 노드의 값 보단 항상 크며, 오른쪽 노드의 값 보단 항상 작다.
그리고 딸린 곁가지 노드가 있는 경우의 수는 다음과 같다.
1. 왼쪽 오른쪽 노드 모두 존재
2. 둘 중 하나만 존재
    2-1. 왼쪽 노드만 존재
    2-2. 오른쪽 노드만 존재
2. 번의 경우엔, Parent라는 변수와, Child라는 변수로 얼추 탐색이 가능하다.
그러나 1번의 경우에는 어떤 식으로 두 갈래의 방향을 탐색해야 할지 감이 잡히지 않는다. 

내가 생각하는 해결책

3가지 경우의 수를 다 처리하는 로직을 구현하고
그 함수를 재귀적으로 호출하는 방식으로 하면 전체 노드를 모두 탐색할 수 있지 않을까?
아님 말고

 

2. 자기보다 큰 수들의 합과 자기 자신의 합을 해당 자리에 노드로 잡는 GBT 

https://leetcode.com/problems/convert-bst-to-greater-tree/

Convert BST to Greater Tree - LeetCode

소감

그냥 문제부터 이해가 가지 않는 미디엄 난이도의 문제였다. 이진 탐색이 이론으로 알고 있을 땐 쉬울 거라 생각했는데, 막상 문제로 보니 이해조차 되지 않는 괴물이란 것을 느꼈다. 요약하자면, 전체 이진 탐색 트리가 있으면, 그 해당 자리를 원래 수와 원래 수보다 큰 수들의 합으로 채운 큰 이진탐색트리(Greater Binary search Tree)를 만드는 메서드를 작성하는 것이다. 문제를 이해하는데만 1시간을 쓴 관계로, 이해하는데 모든 전력을 쏟았다. 거짓말처럼 그만 보게 되었다. 

겪은 어려운 점

첫째도 문제 이해, 둘째도 문제 이해, 셋째도 문제 이해

내가 생각하는 해결책

이진 탐색을 하는 기초적인 방법을 정립을 하고, 그 다음에 고민을 하는 것이 좋겠다. 

3. 배열 X 2

https://leetcode.com/problems/concatenation-of-array/submissions/

Concatenation of Array - LeetCode

소감

세문제를 다 못풀면 자존감이 떨어질껏 같아서 문제 답변율 90%가 넘는 문제를 하나 골랐습니다. 
숫자형 배열을 똑같이 반복하는 문제입니다.
예시
Input: [1,2,3]
output: [1,2,3,1,2,3]

겪은 어려운 점

고차함수 (map, reduce, filter)를 사용해서 풀려 했는데, 귀찮아진 관계로,

해결방법

 forEach 를 사용해서 해결했습니다.
PS) 숫자형 배열도 + 연산자가 사용이 가능합니다...ㅋㅋㅋ