오늘 할일
1. 인공지능개론 11주차 과제, 수기과제
2. 영상처리 과제 마무리
3. LeetCode
4. 영상처리 공부
오늘 한일
- LeetCode
- Delete Node in a BST을 디버깅하기 위해 순서를 따라가며 'check'를 출력하도록 하였다.
문제가 된 79번 테스트 케이스의 문제는 삭제할 대상의 노드와 swap할 노드를 찾아 swap하고 분리하는 replacce_and_diisconnect 함수에 있었다.
노드가 오른쪽->오른쪽, 왼쪽->왼쪽 처럼 특정 방향으로밖에 없을 경우 대체가능한 노드를 찾지 못해 반대쪽의 자식노드로 대체하는 문제가 발생하고 있었다. 이를 if(node.right.left==null)과 if(node.left.right==null)로 핸들링하여 해당 경우를 따로 처리하였다.
private void replace_and_disconnect(TreeNode parent, TreeNode node){//삭제할 대상의 부모노드, 삭제할 대상노드. 대상노드를 대체할 최적값을 찾음
TreeNode victim_1, victim;//삭제대상 노드와 swap될 대상노드의 부모노드
if(parent.right==node){//swap 대상노드 탐색을 위한 방향설정
System.out.println("check");
if(node.right.left==null){
victim_1=node;
victim=node.right;
parent.right=victim;
victim.left=node.left;
} else {
victim_1=left_1(node);//swap대상 노드의 부모노드
victim=victim_1.left;//swap대상 노드
victim_1.left=null;//disconnection
node.val=victim.val;//swap
}
} else {
if(node.left.right==null){
victim_1=node;
victim=node.left;
parent.left=victim;
victim.right=node.right;
} else {
victim_1=right_1(node);
victim=victim_1.right;
victim_1.right=null;
node.val=victim.val;
}
}
}
다음은 85번 테스트 케이스에서 문제가 발생하였다.
의외로 쉬운 문제처럼 보이는데, 디버깅을 해보니 삭제 대상 노드를 찾은 이후, 노드의 자식 개수에 따른 분기처리를 수행하는 branch_per_child_node함수에서 문제가 발생하고 있었다.
else {
//루트노드가 삭제 대상이어서 parent와의 disconnet가 필요하지 않다면
System.out.println("check");
if(node.right==null)
return;
TreeNode victim_1=left_1(node.right);
TreeNode victim;
if(victim_1==null){//루트노드 삭제
victim_1=node;
victim=node.right;
this.rt=victim;
this.rt.left=victim_1.left;
} else{
victim=victim_1.left;
victim_1.left=null;
node.val=victim.val;
}
}루트노드를 삭제하는 경우 해당 노드의 자식의 개수와 관계없이 무조건 오른쪽 노드가 null일 경우 return하여 종료하게끔 코드를 작성하였다. if(node.right==null && node.left!=null)인 경우 루트노드를 node.left로 변경하는 코드를 추가해보자.
다음은 87번 테스트 케이스에서 문제가 발생했다. 아마 오늘 디버깅을 수행하여 TDD방식으로 범용적인 예외처리를 수행하지 않았기에 미처 다루지 못한 케이스에서 문제가 발생했다고 추측해본다.
빨간 노드를 삭제하는 경우에서 올바른 답은 우측에서 가장 가까운 34지만, 나는 좌측의 최좌측값을 swap하였다. 간단한 논리오류일 것이라 추측된다.
디버깅 결과 삭제 대상노드와 swap할 대체값을 찾고 연결을 끊는 replace_and_disconnect함수에서 33과 34가 swap될 때 34의 자식을 그냥 버려버리고 있었다.
이를 정상적으로 연결해주자.!
이번 문제를 해결하는데에 정말 오랜 시간이 걸렸다. 다만 바로 위에 연결한 코드를 보면 알다시피, 대상노드의 자식노드가 왼쪽에 있을수도, 오른쪽에 있을수도 있다. 즉 테스트 케이스가 부족해서 혹은 내가 모르는 BST의 또다른 규칙때문에 통과된 것으로 보인다.
여기서 놀라웠던 점은 시간복잡도이다. 최대한 효율적으로 작성해보려 코드의 길이가 약 150줄로 길어지긴 했지만 그만큼 의미가 있던 코딩인 것 같다. 애초에 탐색하며 부모노드간의 연결이 필요한 경우 부모노드를 리턴시켜 처리하게끔 했고, 최대한 분기별로 함수를 만들어 가독성을 높이려 했다. 마지막에 다다라선 분리된 함수마저 분기로 떡칠이 되어 알아보기 어렵지마는 정말 오랜 시간이 걸려서 이 문제를 좋은 성적으로 해결한 보람이 있다:)
아쉬운 점은 코드의 길이, 가독성, 모듈화, BST의 이해, 공간복잡도 정도가 있다. 시험기간 포함해서 근 한달걸렸네..
class Solution {
private TreeNode rt;
private void replace_and_disconnect(TreeNode parent, TreeNode node){//삭제할 대상의 부모노드, 삭제할 대상노드. 대상노드를 대체할 최적값을 찾음
TreeNode victim_1, victim;//삭제대상 노드와 swap될 대상노드의 부모노드
if(parent.right==node){//swap 대상노드 탐색을 위한 방향설정
if(node.right.left==null){
victim_1=node;
victim=node.right;
parent.right=victim;
victim.left=node.left;
} else {
if(node.right!=null){
System.out.println("check");
victim_1=left_1(node.right);//swap대상 노드의 부모노드
victim=victim_1.left;//swap대상 노드
victim_1.left=victim.right;//disconnection gdgdgd
node.val=victim.val;//swap
} else {
victim_1=left_1(node);//swap대상 노드의 부모노드
victim=victim_1.left;//swap대상 노드
victim_1.left=null;//disconnection
node.val=victim.val;//swap
}
}
} else {
if(node.left.right==null){
victim_1=node;
victim=node.left;
parent.left=victim;
victim.right=node.right;
} else {
if(node.left!=null){
victim_1=right_1(node.left);
victim=victim_1.right;
victim_1.right=victim.left;//dgdg
node.val=victim.val;
} else {
victim_1=right_1(node);
victim=victim_1.right;
victim_1.right=null;
node.val=victim.val;
}
}
}
}
private TreeNode get_parent_node(TreeNode cur, TreeNode node){//탐색을 시작하고 싶은 노드, 탐색하고자하는 노드로 부모노드 탐색
if(cur.left==node || cur.right==node)//현재 cur이 node의 부모노드일 때
return cur;
if(cur.val<node.val)//이진분류에 따른 재귀호출
return get_parent_node(cur.right, node);
else if(cur.val>node.val)
return get_parent_node(cur.left, node);
else{//탐색 실패
System.out.println("루트로부터 노드탐색 실패");//루트가 대상일 때
return null;
}
}
private void branch_per_child_node(TreeNode node){//삭제대상의 노드를 찾았을 때, 해당 노드의 자식 개수에 따른 작업 분기처리
TreeNode parent=get_parent_node(this.rt, node);//삭제 대상의 부모노드
if(parent!=null){//삭제하고자하는 노드가 루트노드가 아니라면
if(node.left==null && node.right==null){//삭제 대상 노드의 자식이 없을 경우
if(parent.left==node)//부모와의 연결을 끊음
parent.left=null;
else
parent.right=null;
} else if(node.left==null && node.right!=null){//삭제 대상 노드의 자식이 1개일 경우
if(parent.left==node)//부모와 삭제대상 자식노드와 연경
parent.left=node.right;
else
parent.right=node.right;
} else if(node.left!=null && node.right==null){//삭제 대상 노드의 자식이 1개일 경우
if(parent.left==node)//부모와 삭제대상 자식노드와 연결
parent.left=node.left;
else
parent.right=node.left;
} else {//삭제 대상 노드의 자식이 2개일 경우
replace_and_disconnect(parent, node);//대체값을 찾고 연결을 끊는 함수 호출
}
} else {
//루트노드가 삭제 대상이어서 parent와의 disconnet가 필요하지 않다면
if(node.right==null&& node.left!=null){
this.rt=node.left;
return;
}
if(node.right==null)
return;
TreeNode victim_1=left_1(node.right);
TreeNode victim;
if(victim_1==null){//루트노드 삭제
victim_1=node;
victim=node.right;
this.rt=victim;
this.rt.left=victim_1.left;
} else{
victim=victim_1.left;
victim_1.left=null;
node.val=victim.val;
}
}
}
private void remove(TreeNode node, int key){//삭제를 위한 본격적 함수_우선적으로 삭제할 노드의 값을 탐색한다.
if(node==null)//찾는 값이 없음
return;
if(node.val<key){//현재 노드가 키값보다 작은 경우
remove(node.right, key);
} else if(node.val>key){//현재 노드가 키값보다 큰 경우
remove(node.left, key);
} else if(node.val==key){//삭제대상을 찾은 경우
branch_per_child_node(node);//대상의 자식 노드 개수에 따른 분기를 처리
} else {//값이 없는 경우
//아무 일도 처리하지 않음
}
}
private TreeNode left_1(TreeNode node){
if(node.left==null)
return null;
if(node.left!=null && node.left.left==null)
return node;
return left_1(node.left);
}
private TreeNode right_1(TreeNode node){
if(node.right==null)
return null;
if(node.right!=null && node.right.right==null)
return node;
return right_1(node.right);
}
public TreeNode deleteNode(TreeNode root, int key){
if(root==null)//루트가 비어있을 경우
return null;
if(root.left==null && root.right==null && root.val==key)//루트의 자식이 없고 루트가 삭제 대상일 경우
return null;
this.rt=root;//루트노드 멤버변수로 설정. 재귀형식으로 함수를 작성할거기에 다양한 접근이 필요.
remove(root, key);//실질적인 삭제작업 수행
return this.rt;
}
}