JAVA 자료구조 : 이진검색트리 중복노드 제거하기

스터디사이트 : https://www.hackerrank.com

JAVA 자료구조 : 이진검색트리 중복노드 제거하기

주어진 코드 중 removeDuplicates 메소드를 완성하라.

= 이진검색트리 입력값이 중복된다면, 중복된 값을 제거하고 출력하라.

앞선 시간에서 여러 번 해왔던 

LinkedList의 이진검색트리  를 응용한 문제라고 볼 수 있다.

※ 주어진 코딩

지정한 영역에서만 코딩하시오

class Node{
    int data;
    Node next;
    Node(int d){
        data=d;
        next=null;
    }
    
}
class Solution
{
    public static Node removeDuplicates(Node head) {
      * Write your code here *
    }
 
    public static  Node insert(Node head,int data)
     {
        Node p=new Node(data);            
        if(head==null)
            head=p;
        else if(head.next==null)
            head.next=p;
        else
        {
            Node start=head;
            while(start.next!=null)
                start=start.next;
            start.next=p;
 
        }
        return head;
    }
 
    public static void display(Node head)
        {
              Node start=head;
              while(start!=null)
              {
                  System.out.print(start.data+" ");
                  start=start.next;
              }
        }
        public static void main(String args[])
        {
              Scanner sc=new Scanner(System.in);
              Node head=null;
              int T=sc.nextInt();
              while(T-->0){
                  int ele=sc.nextInt();
                  head=insert(head,ele);
              }
              head=removeDuplicates(head);
              display(head);
 
       }
}

입력

6

1

2

2

3

3

4

출력

1 2 3 4

디버깅

removeDuplicate메소드의 모든 내용과 display메소드의 일부분만 수정해서 디버깅 해보았다

public static Node removeDuplicates(Node head) { Node temp=head; while(temp.next != null) { System.out.println("----------------------------\ntemp.data : " + temp.data ); if(temp.data==temp.next.data){ // temp값과 temp다음 노드의 값이 같다면 System.out.println("temp값과 temp다음 노드의 값이 같다"); temp.next=temp.next.next; System.out.println("temp.next.next를 temp.next로 치환: " + temp.data); }else{ System.out.println("temp값과 temp다음 노드의 값이 같지 않다."); temp=temp.next; System.out.println("다음 temp로 포인터 이동: " + temp.data); } } //end while return head; } //end method removeDuplicates public static void display(Node head) { System.out.println("\n----------display------------"); Node start=head; while(start!=null) { System.out.print(start.data+" "); start=start.next; } } //end method display

입력 :  6 1 2 2 3 3 4 결과 :  ---------------------------- temp.data : 1 temp값과 temp다음 노드의 값이 같지 않다. 다음 temp로 포인터 이동: 2 ---------------------------- temp.data : 2 temp값과 temp다음 노드의 값이 같다 temp.next.next를 temp.next로 치환 : 2 ---------------------------- temp.data : 2 temp값과 temp다음 노드의 값이 같지 않다. 다음 temp로 포인터 이동: 3 ---------------------------- temp.data : 3 temp값과 temp다음 노드의 값이 같다 temp.next.next를 temp.next로 치환 : 3 ---------------------------- temp.data : 3 temp값과 temp다음 노드의 값이 같지 않다. 다음 temp로 포인터 이동: 4 ----------display------------ 1 2 3 4

결과

class Node{ int data; Node next; Node(int d){ data=d; next=null; } } class Solution { public static Node removeDuplicates(Node head) { Node temp=head; while(temp.next != null) { if(temp.data==temp.next.data){ temp.next=temp.next.next; }else{ temp=temp.next; } } //end while return head; } public static Node insert(Node head,int data) { Node p=new Node(data); if(head==null) head=p; else if(head.next==null) head.next=p; else { Node start=head; while(start.next!=null) start=start.next; start.next=p; } return head; } public static void display(Node head) { Node start=head; while(start!=null) { System.out.print(start.data+" "); start=start.next; } } public static void main(String args[]) { Scanner sc=new Scanner(System.in); Node head=null; int T=sc.nextInt(); while(T-->0){ int ele=sc.nextInt(); head=insert(head,ele); } head=removeDuplicates(head); display(head); } }

입력 :  6 1 2 2 3 3 4 결과 :  1 2 3 4