b. 자식 노드는 보통 왼쪽과 오른쪽으로 구분한다 -> left child, right child
c.각 노드는 데이터를 가지고 있다. (데이터를 저장하기 위한 자료구조 중 하나이니 당연한 말이다)
- 이진탐색트리(Binary Search Tree, BST)의 특징
a. 이진트리이므로 이진트리의 특성을 기본적으로 갖고 있다.
b.각 노드의 값은 왼쪽 서브트리에 존재하는 모든 값들 보다 크고 오른쪽 서브트리에 존재하는 모든 값들 보다 작다.
c. 따라서 이진탐색트리는 정렬된 이진트리(sorted binary tree)라고도 한다.
자, 그리고 여기에 추가로 아래와 같은 특징을 갖는 트리를 AVL 트리라고 부릅니다.
- AVL 트리의 특징
a. 어떤 노드라도 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않다. (최대 높이 차이는 1 이다.)
=> Binary Tree이면서 최대 높이 차이가 1이라는 말은 height = O(log N) 이라는 것과 같다.
b. 만약 특정 노드를 추가하거나 삭제했을 때 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 커지는 노드가 생긴다면, re-balancing을 통해 a 규칙에 어긋나지 않도록 한다.
=> 이 말은 AVL 트리는 자가 균형 이진 탐색 트리(self-balancing BST) 라는 말과 같다.
c. 균형 트리(balanced tree)이다. (좀더 정확히는 높이 균형 트리이다.)
=> 균형 트리는 아래 세 가지 조건을 모두 만족하는 트리이다.
i. 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이다.
ii. 왼쪽 서브트리가 균형 트리이다.
iii. 오른쪽 서브트리가 균형 트리이다.
d. 각 노드는 균형값(균형인수, balance factor)을 가지고 있으며 이 균형값은 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. 이 값은 항상 {-1, 0, 1 } 셋 중 하나의 값이어야 한다.
e. 균형값(균형인수, balance factor)이 마이너스(-)이면 left-heavy, 플러스(+) 값을 가지면 right-heavy 라고 한다.
f. pivot 노드는 새로운 노드가 추가되었을 때 균형값에 변동이 발생하여 unbalanced 된 노드들 중 신규노드와 가장 가까운 노드를 말한다.
자, 위와 같은 특징을 갖고 있는 AVL 트리에 노드를 추가 또는 삭제를 하게되면 스스로 균형을 맞추기 위해 트리의 회전(rotation)을 필요로 할 수도 있습니다. 노드가 추가 또는 삭제 되면서 일부 노드들의 균형값에 변동이 발생하기 때문입니다. 회전을 필요로 하는 경우는 크게 2가지(single rotation과 double rotation) 좀 더 세분화하면 아래와 같이 4가지로 나눌 수 있습니다.
왼왼 (Left - Left) : 부모 노드와 pivot 노드의 균형값이 모두 left-heavy인 경우 => Single Right rotation (오른쪽으로 1회전)
오오 (Right - Right) : 부모 노드와 pivot 노드의 균형값이 모두 right-heavy인 경우 => Single Left rotation (왼쪽으로 1회전)
왼오 (Left - Right) : 부모 노드와 pivot 노드의 균형값이 각각 right-heavy, left-heavy, 인 경우 => Double Left-Right rotation (왼쪽으로 한번, 오른쪽으로 한번 총 두 번의 회전)
오왼(Right - Left) : 부모 노드와 pivot 노드의 균형값이 각각 left-heavy, right-heavy인 경우 => Double Right-Left rotation (오른쪽으로 한번, 왼쪽으로 한번 총 두 번의 회전)
각각의 로테이션에 대한 그림은 wiki에 매우 간단하게 나와있어 gif 이미지를 첨부합니다.
로테이션 예제 그림이 너무 간단해서 위 4가지 케이스에 대해 설명이 잘 될지 모르겠습니다.
로테이션에 대한 추가 설명은 다음 포스팅을 기다려주세요~
추가로 AVL 트리에 새로운 노드를 추가하거나 삭제하는 동작은 최악의 상황에서도 O(log N) 의 시간복잡도를 보이며 검색 또한 O(log N) 으로 빠른 자료구조입니다.
문제에서는 span이라는 것을 "가장 왼쪽에 있는 특정 값 a와 가장 오른쪽에 있는 동일한 값 a 사이의 길이" 라고 설명하고 있습니다. 이때 이 길이에는 가장 왼쪽값과 가장 오른쪽 값의 위치를 포함한 길이입니다.
즉, int[ 1, 2, 1 ] 을 인자로 받았을 경우 1에 대한 span은 3이 됩니다.
가장 왼쪽의 1과 가장 오른쪽의 1을 포함한 길이가 되는 것이죠.
만약 int[ 1, 2, 1, 3, 4, 2 ]를 인자로 받았다면,
1에 대한 span = 3
2에 대한 span = 5
3에 대한 span = 1
4에 대한 span = 1
이 됩니다.
이렇게 계산했을 때 maxSpan은 2에 대한 span값인 5가 됩니다.
제가 풀어본 해답은 아래와 같습니다.
뭐 그냥 루프를 중복으로 돌려서 해결했는데 이건 정말 최악의 해답이 되겠죠.
왠만하면 중복 루프를 사용하면 안됩니다. 속도저하가 상당하니까요.
문제에서 말하길 속도는 신경쓰지 않아도 된다고 해서 그냥 바로 생각나는 대로 문제를 풀어보았습니다.
O(n제곱)이 되지 않도록 하기 위해서 이미 체크했던 숫자인지에 대한 정보를 가지고 있도록 했습니다.
위에서 든 예제를 인용해서 설명드리자면,
int [ 1, 2, 1, 3, 4, 2 ]를 인자로 받았을 경우에 1과 2는 각각 두번씩 들어가있는데요
이때 두번째로 나오는 숫자들에 대해서는 사실 계산할 필요가 없죠. 이미 첫번째로 나온 1과 2를 만났을 때 span값을 계산하기 때문이죠. 동일한 숫자들이 두개 이상 나오게된다면 이미 검사했던 숫자들에 대한 span을 구하기 위해서 불필요한 계산을 하게 됩니다. 이런 계산을 없애기 위해서 한번 체크했던 숫자와 동일한 숫자를 outer most for loop에서 만나게되면 체크했던 숫자인지를 검사하는 first inner loop를 돌고 체크했던 숫자가 아닌 경우에만 second inner loop에서 처리하게 됩니다.
또한, second inner루프에서 처리를 할 때에도 int[]의 현재 숫자의 위치에서 오른쪽에 있는 숫자들을 가지고 비교를 합니다. 좌측에 있는 숫자들 중에는 이 숫자와 동일한 숫자가 없다는 전제가 필요한데 이 전제를 바로 위에 설명드린 first inner loop에서 처리를 해주고 있기 때문이죠.
이런식으로 하게될 경우 최악의 경우( int[]에 들어있는 숫자가 모두 다를 경우 )에도 O(n제곱) 까지는 안가게 됩니다.
중복 for loop를 사용하기는 했지만 나름 속도도 신경을 쓴 로직이라고 말할 수 있죠.
public int maxSpan(int[] nums) { if ( nums.length == 0 ) return 0; int maxSpan = 1; int[] checkedNumbers = new int[nums.length]; int checkedNumbersPos = 0;
// Outer Most For Loop
for ( int i = 0; i < nums.length ; i++ ){ boolean checked = false;
// First Inner Loop for( int checkedItem : checkedNumbers ){ if ( checkedItem == nums[i] ){ checked = true; } } if ( !checked ){ checkedNumbers[checkedNumbersPos] = nums[i];
// Second Inner Loop for ( int j = i + 1; j < nums.length ; j++ ){ if ( nums[j] == nums[i] ){ int tempSpan = j - i + 1; if ( tempSpan > maxSpan ){ maxSpan = tempSpan;} } } } } return maxSpan; }
public int noTeenSum(int a, int b, int c) { int sum = 0; sum += fixTeen(a); sum += fixTeen(b); sum += fixTeen(c); return sum; } public int fixTeen(int n){ if ( n > 12 && n < 20 ){ if ( n != 15 && n != 16 ){ return 0; } } return n; }