흥미로운 IT

트리 이론을 공부한 후 가장 처음으로 건드려보려고 한 문제가 바로 이 문제다.

preorder (root --> left --> right) traversal의 순서는 알았지만, 

정확히 이것을 리스트로 받고 처리를 하는 것인지에 대해서 고민이 많았다.

그리고 현재 계속 "재귀"에 대한 이해를 제대로 잡고 가기 위해서 이번에는 재귀를 제대로 잡자는 생각으로 재귀로 코드를 짜 보고자 하였다.

우선 과거에 자료구조를 공부할 때, C언어로 잠깐했었는데, 언뜻 기억났던 코드가 바로 다음과 같은 코드였다.

void traversal(node){
    if ( node){
        visit(node); preorder
        traversal(node -> left);
        #visit(node); inorder
        traversal(node -> right);   
        #visit(node); postorder
    }  
}

그럼 위의 코드를 이제 리트코드에 준 문제에 맞게 만들어야 했는데,

정말로 고민을 많이 했다.

어디서 어떻게 코드가 들어가야 하고,

재귀는 정확히 어떻게 이루어지는지가 고민이었다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        visited = []
        if root is not None:
            visited.append(root.val)
            # print(root.val, "afterAppend", visited)
            visited.extend(self.preorderTraversal(root.left))
            # print(root.val, "afterLeft", visited)
            visited.extend(self.preorderTraversal(root.right))
            # print(root.val, "afterRight", visited)
        return visited

여기서 visited.extend도 핵심이다.

처음에 나는 그냥 self.preorderTraversal(root.left)라고 했었다.

그런데 이렇게 하다보니, visited를 return 했을 때, 제대로 이 값들을 추가를 시켜주지 못했다.

그러다 보니 답이 [1]에서 멈춰있었다. 

그래서 제대로 어떻게 코드가 처리되고 있는지를 알기 위해서 위에 주석 처리된 print문들을 찍게 되었고,

이를 직어보니 [1] [2] [3]과 같이 재귀를 돌 때 제대로 숫자는 리턴 하지만,

최종적으로 값들을 하나의 리스트에 저장하지 못했다는 점이 있었다.

따라서, 이를 해결하기 위해서, 재귀를 해서 리턴하는 값을 리스트에 넣는 코드로 수정이 필요했고,

이를 위해. extend()를 사용하게 되었다.

아직도 해당 코드를 보아도 제대로 이해를 했다고 보기는 어려운 것 같다.

다른 사람에게 설명하라고 하면 내가 제대로 설명을 하고 있는가에 대해서 스스로 의문을 가지고, 

설명하는 도중에도 왠지 막힐 것 같다는 생각이 든다.

따라서, 해당 문제는 계속 더 공부가 필요하다고 느낀다.

최근에 트리 이론과 재귀를 제대로 이해하고 이제 직접 코딩으로 구현을 해보는 연습을 하고 있는 중이다.

그 중에 내가 풀어놓고 답인지 아닌지 햇갈렸던 문제 중 하나가 위의 문제였다.

일단 답은 다음과 같이 간단하게(?) 구현이 가능하다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        else:
            return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

일단 if not root 부분은 base 코드, 즉 재귀를 끝내기 위한 코드인 것은 금방 추론이 가능하다.

문제는 return 부분이다.

최대한 쉽게 말로 풀이를 해보자면 이렇게 된다.

1. 우선 3으로 root가 시작된다
2. 3의 root.left는 9가 된다.
3. self.maxDepth(root.left)에는 9가 들어가는 것이므로, maxDepth(self, 9)가 된다.
4. 9가 들어오면 일단 다시 else문으로 가게 된다.
5. 9일 때, self.maxDepth(root.left)와 self.maxDepth(root.right)는 둘 다 null이므로, return max(0, 0)+1이 되므로 return 1이 된다.
6. 따라서 이제 9일 때 1이 나오기 때문에 재귀한 것을 타고 올라가면, 맨 처음 root가 3이었을 때, max(1, self.maxDepth(root.right))+1인 것을 알 수 있다.
7. 이제 self.maxDepth(root.right)도 똑같이 해주면 (이 경우에는 20이 들어가고, 들어간 후 각각 15, 7이 나올 것이다)), 결국 root가 3이었을 때, return self.maxDepth(1,2)+1이 된다.
8. 따라서, 결론적으로는 return 2+1 즉, return 3이 나온다.

재귀는 계속 풀어봐야하는 것을 느낀다.

과거에 여러 번 코딩테스트 시도를 실패했던 첫 번째 관문 중 하나가 나에게는 항상 재귀였다 (이를 활용한 트리도...).

계속 여러 문제를 이번에는 끈덕지게 풀어보고자 한다.

이 문제도 시간이 많이 걸렸다.

최근에 느낀 것이지만 문제를 풀 때 이상하게 append와 pop을 많이 사용하는 경향이 있었는데,

왜 그런가 고민해보니 C언어스럽게 나도 모르게 파이썬 코드를 짜고 있었다는 것을 알게 되었다.

스트링이나 숫자들을 모두 리스트에 넣고, 리스트의 인덱스를 사용해서 만드는 방법이 대표적으로 C언어스럽다는 것이다.

이 문제도 결국 그렇게 풀고,

문제 푼 코드의 지저분함을 느끼고 계속 쳐다본 결과 그렇게 된 것 같다.

그리고 코드를 볼 때 참고해야할 사항이 몇 가지 있는데...

1. 조건인 constraint를 제대로 읽지 않았다. 알고보니 testcase의 입력값들이 모두 양수로 되어있다는 것이었다. 음수값의 경우도 모두 처리해야하는 줄 알고 if elif else문을 사용했다.

2. contraint를 알고 원래 만들었던 코드를 그대로 사용해보았더니 그래도 지저분했다.

3. 그래서 파이써닉한 코드를 한 번 만들어보고 "remove()" 함수를 알게 되어 "pop"대신 사용할 수 있게 되었다.

-그동안 pop()을 계속 사용한 이유는 remove()를 제대로 몰랐기 때문.

-pop()은 index값을 넣어야 하고, remove()는 지우고자 하는 숫자/문자를 넣으면 된다.

4. 마지막의 코드는 sort()를 사용한 것인데, 가장 간단하고 직관적인 코드이다. 다만, 효율성을 배제하고 생각해야 한다. 시간적인 면에서는 가장 느리다는 특징이 있다.

#constraint 제대로 확인 안하고 음수까지 모두 처리 (77ms)
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums_abs = [abs(ele) for ele in nums] # 절대값으로 바꾼다. O(n)
				nums_abs is ...
				list of abs(ele) for each ele in nums
				dictionary of ...

        top_maxIndex = nums_abs.index(max(nums_abs))
        top_positive_max = nums_abs.pop(top_maxIndex)
        next_maxIndex = nums_abs.index(max(nums_abs))
        next_positive_max = nums_abs.pop(next_maxIndex)


        if nums[top_maxIndex] > 0 and nums[next_maxIndex] > 0:
            return ((top_positive_max-1) * (next_positive_max-1))
        elif nums[top_maxIndex]<0 and nums[next_maxIndex]<0:
            return ((top_positive_max-1) * (next_positive_max-1))
        else:
            if nums[top_maxIndex] < 0:
                nums.pop(next_maxIndex)
                # print("if", nums[top_maxIndex])
                return ((max(nums)-1) * (next_positive_max-1))
            else:
                nums.pop(top_maxIndex)
                # print("else", nums[next_maxIndex])
                # print((max(nums)))
                return ((max(nums)-1) * (top_positive_max-1))



# constraint 제대로 보고 처리하면 다음과 같은 코드 가능(66ms)
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        top_maxIndex = nums.index(max(nums))
        top_positive_max = nums.pop(top_maxIndex)
        next_maxIndex = nums.index(max(nums))
        next_positive_max = nums.pop(next_maxIndex)
        return ((top_positive_max-1) * (next_positive_max-1))

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
		mx = max(nums)
		nums.remove(mx)

		next_mx = max(nums)
		# nums.remove(next_mx)

		return (mx-1)*(next_mx-1)


# 더 짧고 빠르게 sort()를 활용하여 하면 다음과 같은 코드
# 그런데 sort() 함수가 속도가 많이 느린 것인지 속도 자체는 위의 2개의 코드 중 제일 느리게 나온다 (101ms)
# 효율성을 떠나 가장 파이썬스러운 코드
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        nums.sort()
        return (nums[-1]-1) * (nums[-2]-1)

출처: https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/

해당 문제를 굉장히 헤맸다.

총 8번을 틀렸는데...

wrong answer는 총 3가지의 경우 때문에 나왔다.

(1) len(nums) <= k에서 =를 실수로 넣지 않아서

(2) update_max/k 를 update_max만 리턴해서

(3) 음수를 염두해야하는데 특정 변수의 초기값을 0으로 해놓고 코드에서 제대로 업데이트를 시켜주지 않아서

time limit exceeded 3번이 정말로 힘들었다.

계속 여러 번 시도해본 결과 문제는 아마도 sums를 계속 k개의 숫자만큼 계산을 n.length-(k-1)만큼 반복하게 해서 그런듯 하다.

오류의 코드는 다음과 같다.

#Time Limit Exceeded
nums_four_list = []
total = []
if len(nums) == k:
    print(sum(nums)/k)
for i in range(len(nums)-(k-1)):
    nums_four_list = nums[i:i+k]
    total.append(sum(nums_four_list))

print(max(total)/k)

#Time Limit Exceeded
initial_max_total = sum(nums[0:k])
new_max = 0
update_max = 0
if len(nums) < k:
    print(sum(nums)/k)
for i in range(len(nums)-(k-1)):
    # print(update_max)
    new_max = sum(nums[i:i+k])
    if i == 0:
        if new_max >= initial_max_total:
            update_max = new_max
            newmax = 0
    else:
        if new_max > update_max:
            update_max = new_max
            newmax = 0

print(update_max/k)

#Time Limit Exceeded
update_max = sum(nums[0:k])
new_max = -9999999
update_max = -9999999
if len(nums) <= k:
    print(sum(nums)/k)
    
for i in range(len(nums)-(k-1)):
    new_max = sum(nums[i:i+k])
    if new_max > update_max:
        update_max = new_max
    # print(update_max)

# print(update_max/k)
print(update_max/k)

계속 틀리다가 결국 solution을 보게 되었다.

solution에서 주는 하나의 풀이는 sums의 계산을 단 1번만 초기에 하고,

반복적으로 {

현재값과 다음 index의 값을 더한 후, 이전에 구했던 index들 중 가장 초기값을 빼는 것 ----- (a)

그리고 이렇게 구한 이전의 max값과 (a)의 결과를 max를 통해 구한 후,

이를 best값으로 정한다.

}

## solution
best = 0
now = sum(nums[0:k])
best = now
for i in range(k,len(nums)):
    now += nums[i] - nums[i-k]
    best = max(best,now)
print(best/k)

확실히 solution을 보니 time limit exceeded가 나온 나의 코드보다 훨씬 계산이 줄어들었다는 것을 깨달았다.

이런 형태를 아마 "sliding window"라고 하는 듯하다.

이런 문제해결 방법은 아예 생각을 하지 못했으니 후회는 없지만,

확실히 아쉽다는 생각이 든다.

출처: https://leetcode.com/problems/maximum-average-subarray-i/