[면접 스터디] 선형자료구조2

litien·2019년 9월 29일
0

면접 스터디

목록 보기
3/4

1. 정렬되어 있지 않은 링크드리스트에서 중복된 원소를 없애라

  • 임시 버퍼를 사용 할 수 있을 때
    링크드리스트를 순회하면서, Hash 테이블에 저장 Hash 테이블에 이미 저장된 데이터라면 삭제한다. 시간복잡도는 O(n)이 소요된다.
    	void deleteDups(LinkedListNode n) {
          HashSet set = new HashSet();
          LinkedListNode previous = null;
          
          while(n != null) {
            if(set.contains(n.data) {
              previous.next = n.next; // 노드 삭제
            } else {
              set.add(n.data);
              previous = n;
            }
            n = n.next;
         }
  • 임시 버퍼를 사용 할 수 없을 때
    버퍼가 없다면 두 개의 포인터를 사용해 문제를 해결 할 수 있다. 현재 포인터와 runner 포인터를 이용해 중복을 제거 할 수 있다. 시간복잡도는 O(N^2)이가 소요된다.
    	void deleteDups(LinkedListNode head){
            LinkedListNode current = head;
            
            while(current != null){
              LinkedListNode runner = current;
              while(runner.next != null){
                if(runner.next.data == current.data){
                  runner.next = runner.next.next;
                } else{
                  runner = runner.next;
                }
              }
              current = current.next;
            }
          }

2. 주어진 링크드리스트가 Palindrome인지 Stack을 이용해 검사하는 방법을 설명하라

두개의 포인터를 이용한다. 하나의 포인터 slow는 한칸 씩 이동하면서 stack에 쌓는다. runner 포인터는 두칸 씩 이동한다. runner 포인터가 끝 부분에 닿으면 stack에는 링크드리스트 절반의 노드가 역순으로 stack에 쌓여있다. 이후부터 stack의 top과 slow를 한칸 씩 이동하면서 비교한다.

	boolean isPalindrome(LinkedListNode head){
      LinkedListNode fast = head;
      LinkedListNode slow = head;
      Stack stack = new Stack();
      
      // 리스트 앞 절반을 스택에 쌓는다.
      while(fast != null or fast.next != null) {
        stack.push(slow.data);
        slow = slow.next;
        fast = fast.next.next;
      }
      
      // node 수가 홀수 개라면 가운데 원소는 넘긴다
      if (fast != null) {
        slow = slow.next;
      }
      
      while(slow != null) {
        int top = stack.pop().intValue();
        if(top != slow.data) {
          return false;
        }
        slow = slow.next;
      }
      return true;
    }

3. LRU를 stack으로 어떻게 구현 할 수 있는지 설명하라

빼고자 하는 임의 값이 나오기 전까지 새로운 Stack을 만들어 저장한다. 빼고자 하는 값을 pop 한 뒤, 새로운 stack의 값들을 하나씩 pop하면서 원래의 stack으로 옮긴다. 그리고 뺀 데이터를 다시 stack에 push한다.

또는 double linked list를 이용해 구현 할 수 있다. 빼고자 하는 Stack의 node까지 찾아간 다음, 해당 노드를 제거하고 head 앞에 넣어준다.

	void moveMidToHead(Node node){
      Node preNode = node.preNode;
      Node nextNode = node.nextNode;
      
      if(preNode != null) {
        preNode.nextNode = nextNode;
      }
      
      if(next != null) {
        nextNode.preNode = preNode;
      } else {
      	this.tailNode = nextNode;
      }
      
      this.headNode = node;
    }
      
profile
어려운 문제를 함께 풀어가는 것을 좋아합니다.

0개의 댓글