inorder traversal와 preorder traversal한 데이터가 들어왔을때 트리를 그리라는 뜻 간단하게 정리하자면 Preorder는 root->left->right 순으로 순회를, Inorder는 left->root->right 순으로 순회를 하는 것이다. 각 traversal 결과에 대해 root를 기준으로 정리할 수 있다. 예컨데 preorder의 경우 root node를 가장 먼저 방문하므로, 3이 root가 되고 이를 inorder에 적용하면 3을 기준으로 9가 left node, 15,20,7은 right node라는 것을 알 수 있다. 따라서 다음과 같은 방식으로 문제를 풀어보려 한다 helper라는 함수를 이용하여 재귀처리 하려고 한다. 이때 사용되는 args는 rootPreI..

트리가 주어지면 이를 Linked-List로 바꾸는 문제이다. 조건에 따라 right node는 next node가 되고, previous는 null이 된다. convertToList라는 함수를 제외하고 보자. Tree니까 재귀를 떠올리고. root가 주어지면, root의 left와 right를 flat하게 만든 후, null- root - left subtree - right subtree 형태로 붙이면된다. 이때 left와 right의 관계를 재귀로 처리해준다. 이제 convertToList를 살펴보면, right가 있는 경우, left.right가 null이 될대까지 모든 left node를 거슬러 내려간다 예컨데 left의 node가 3개라면, first.right는 Loop가 세번 돌아야 존재할..

두 x좌표 사이의 길이와 두 x좌표에 대한 height값 중 최소값을 곱한 값이 최대가 되는 값을 찾아라 전형적인 two-pointer문제다 포인터를 두 개 두고 Loop를 돌며, 각 Loop의 면적값을 구해 global answer와 비교하는 방식이다. 이 문제가 two-pointer인 이유는 간단하게 x좌표가 같거나 작을 수 없으므로 검사가 필요 없기 때문이다. 예컨데 i가3이라면 i보다 작거나 같은 j는 검사할 필요가 없다 다음과 같이 이중for문을 쓰면 timeout 에러가 날 것이다 이렇게 forward와 backward를 정해주고, global answer를 바꿔가며 설정해주면 된다.

string을 정해진 규칙에 따라 decode하는 문제 모양이 정해진 연쇄적인 string을 처리할때에는 stack을 사용한다 다양하게 index를 활용해보았다. 일단 string, number, bracket 섞여있기때문에, 따로따로 분리해서 처리해준다. 이때 loop를 한번 처리할때마다 pt를 증가시키고, pt가 s의 길이와 같아지면 모든 처리가 끝난셈이므로 종료한다 일단 number가 들어오면 currNum에 숫자를 입력해준다 마찬가지로 string이 들어오면 currStr에 추가해준다 괄호가 열리면 currStr과 currNum을 각각 stack에 넣는다. currStr은 앞에서 처리가 끝나서 문자열로 변환된 값이다 다음에 쓰기 위해 일단 보관용으로 넣어둔다 괄호가 닫히면, numStack에 있는..

n개의 노드가 주어졌을때 만들수 있는 BST의 조합 갯수를 구하는 문제이다. Tree의 전형적인 재귀방식으로도 풀 수 있으나, 기본적으론 DP로 풀어낼 수 있다. BTS는 크기에 따라 자연스레 노드가 배치된다. 그러니까 root node만 배치하고 갯수만 나누어주면, 각각의 경우의 수는 고정된다는 뜻이다. 예컨데 다음과 같이 세개의 원소가 주어진다고 해보자. 만약 특정원소를 root로 정한다면, 양옆에 BST를 만들 수 있는 경우의 수는(2개,0개) (1개,1개) (0개,2개)로 나누어지는 방식일것이다. 예컨데 n개의 원소가 존재하고, f(n) 을 n개로 만들 수 있는 BST의 수라고 한다면 f(n) =( f(n)*f(0) ) + ( f(n-1)*f(1) ) + ( f(n-2)*f(2) ) + ( f(n..

전형적인 DP 이전 문제의 솔루션과 유사하다 시작하기전에 모든 [ 0, j ] 와 [ i, 0]을 1로 채워준다. 해당 지점까지 도달하는 방법은 한가지이기 때문이다 일단 i가 0인 element는 모두 1로 채워준다 그 뒤 m개의 행,n개의 열이 존재하므로, 2행부터(1행은 1로 모두 채웠다) 채워준다 이때 모든 [ i , 0 ]자리 역시 1가지 경우의수만 존재하므로 1로 채우고 시작한다.