11 to 9, Day 19

Today, ToDoList

• 리스트 자료구조

• LeetCode - 3. Longest Substring Without Repeating Characters

---

리스트 자료구조

ArrayList

• 검색 시간 복잡도는 O(1)
• 추가 및 삭제 시간 복잡도는 O(1)이지만 최초 수용량 넘어선 작업에 대해서 O(N)이 될 수 있음.
• 특정 인덱스에 추가하는 시간 복잡도는 O(N)
• contains()를 이용한 포함하는지 조회의 시간 복잡도는 O(N)

LinkedList

• 검색 시간 복잡도 O(N)
• 추가 및 삭제 시간 복잡도 O(1) (단 삭제 작업은 개념적으로는 그렇지만 실질적으로는 노드에 있는 값으로 검색해야 하기 때문에 O(N))
• 특정 인덱스에 추가하는 시간 복잡도는 O(N)

package lists;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class LinkedList {

    private LinkedNode head;
    private LinkedNode tail;

    private void add(LinkedNode node) {
        if (head == null) {
            head = node;
            tail = node;
        } else if (tail != null) {
            tail.next = node;
            tail = tail.next;
        }
    }

    private void print() {
        LinkedNode node = this.head;
        while ( node != null ) {
            System.out.println(node.val);
            node = node.next;
        }
    }

    //단일 연결 리스트를 뒤집는 함수 - 순회
    //시간 복잡도 O(N), 공간 복잡도 O(1)
    private void reverse1() {
        LinkedNode current = this.head;
        LinkedNode previous = null;
        LinkedNode next = null;


        while ( current != null ) {
            next = current.next;

            current.next = previous;

            previous = current;
            current = next;
        }

        this.tail = this.head;
        this.head = previous;
    }

    //단일 연결 리스트를 뒤집는 함수 - 재귀
    //시간 복잡도 O(N), 공간 복잡도 O(N)
    private void reverse2() {
        LinkedNode head = this.head;
        this.head = reverseRecursive(head);
        this.tail = head;
    }

    private LinkedNode reverseRecursive(LinkedNode node) {
        if ( node == null || node.next == null ) {
            return node;
        }
        LinkedNode newHead = reverseRecursive(node.next);
        node.next.next = node;
        node.next = null;
        return newHead;
    }

    //단일 연결 리스트에서 끝에서 n번째에 위치한 노드 - 순회
    //시간 복잡도 O(N^2), 공간 복잡도 O(1)
    private LinkedNode findFromLast1(int n) {
        LinkedNode node = this.head;
        LinkedNode next = null;
        while ( node != null ) {
            next = node.next;
            int count = 0;
            while ( next != null ) {
                next = next.next;
                count++;
            }
            if ( count == n - 1 ) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    //단일 연결 리스트에서 끝에서 n번째에 위치한 노드 - 두번 순회
    //시간 복잡도 O(N), 공간 복잡도 O(1)
    private LinkedNode findFromLast2(int n) {
        LinkedNode node = this.head;
        int count=0;
        while ( node != null ) {
            node = node.next;
            count++;
        }
        node = this.head;
        while ( count-n > 0 ) {
            node = node.next;
            count--;
        }
        return node;
    }

    //단일 연결 리스트에서 끝에서 n번째에 위치한 노드 - HashMap
    //시간 복잡도 O(N), 공간 복잡도 O(N)
    private LinkedNode findFromLast3(int n) {
        Map<Integer, LinkedNode> map = new HashMap<>();
        LinkedNode node = this.head;
        int index = 0;
        while ( node != null ) {
            map.put(index++, node);
            node = node.next;
        }

        return map.get(map.size() - n);
    }

    //단일 연결 리스트에서 끝에서 n번째에 위치한 노드 - 순회, 포인터 추
    //시간 복잡도 O(N), 공간 복잡도 O(1)
    private LinkedNode findFromLast4(int n) {
        LinkedNode left = this.head;
        LinkedNode right = this.head;
        int count = 0;

        while ( right != null ) {
            if ( right.next == null) {
                return left;
            }
            right = right.next;

            if ( count + 1 == n ) {
                left = left.next;
            } else {
                count++;
            }
        }

        return null;
    }


    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(new LinkedNode(1));
        list.add(new LinkedNode(2));
        list.add(new LinkedNode(3));
        list.add(new LinkedNode(4));
        list.add(new LinkedNode(5));
        list.add(new LinkedNode(6));
        list.add(new LinkedNode(7));

        System.out.println(list.findFromLast1(3).val);
        System.out.println(list.findFromLast2(3).val);
        System.out.println(list.findFromLast3(3).val);
        System.out.println(list.findFromLast4(3).val);
    }

}

---

LeetCode - 3. Longest Substring Without Repeating Characters

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int length = 0;
        Set<Character> set = new HashSet<>();
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            if ( set.contains(s.charAt(i)) ) {
                while ( s.charAt(index) != s.charAt(i) ) {
                    set.remove(s.charAt(index++));
                }
                index++;
            } else {
                set.add(s.charAt(i));
            }
            length = Math.max(length, set.size());
            System.out.println(length+"  "+set.toString());
        }
        return length;
    }
}