Algorithm Study With Java #2 (JAVA COLLECTIONS)

Collections의 의미와 종류

• Collections란?
  - 자주 쓰는 자료구조로 이미 Java 언어 내부 Collections에 구현되어 있음
• Collections의 종류는?
  - Vector
  - Deque
  - List
  - Set
  - Map
  - Stack
  - Queue
  - ...
  

ArrayList (java.util.ArrayList< E>)

• java.long.Object
  - java.util.AbstractCollection< E>
  - java.util.AbstractList< E>
  - java.util.ArrayList< E>

  public class ArrayList<E>
  extends AbstractList<E>
  implements List<E>, RandomAccess, Cloneable, Serializable

• 길이가 변하는 배열
• C++에서는 Vector에 해당하는 역할
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html
• ArrayList의 생성 방법
  - ArrayList()
  - 단순 생성
  • ArrayList(int initialCapacity)
    • 초기의 크기를 정해줄 수 있음
• ArrayList를 사용할 때 많이 사용하는 메소드
  - boolean add(E e)
  - ArrayList의 뒤에 새로운 Element를 추가하는 것
  - O(N)의 시간이 걸림
  • void add(int index, E element)
    • Index번째에 추가하는 것
  • void clear()
    • ArrayList를 완전히 비워버리는 것
      • O(N)의 시간이 걸림
  • boolean Contains(Object o)
    • 어떠한 Object o가 들어있는지 판단
  • E get(int index)
    • Index번째를 데려오는 메소드
  • boolean isEmpty()
    • 비어있는지 확인하는 것
  • E remove(int index)
    • 특정 index의 Element를 지우는 것
      • O(N)의 시간이 걸림
  • E set(int index, E element)
    • 특정 index의 Element를 새로운 Element로 재배정하는 것
  • Object[] toArray()
    • ArrayList를 Array로 바꿈
• ArrayList의 사용 예 1
  - 수 정렬하기 (https://www.acmicpc.net/problem/2750)

  		import java.util.*;
  		public class Main {
    public static void main(String args[]){
  			Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      ArrayList<Integer> a = new ArrayList<Integer>();
      for (int i=0; i<n; i++) {
        int temp = sc.nextInt();
        a.add(temp);
      }
      Collections.sort(a);
      for(int x : a) {
        System.out.println(x);  
      }
    }
  }

• ArrayList의 사용 예 2
  - 그래프 문제의 인접 리스트 만들기에 가장 많이 사용한다.
  • 인접 리스트란?
    • ArrayList의 배열
    • https://kingpodo.tistory.com/46

	ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
	// ArrayList의 배열 만들기

	for (int i=1; i<=n; i++) {
      a[i] = new ArrayList<Integer>();  
    }

    for (int i=0; i<m; i++) {
      int u = sc.nextInt();
      int v = sc.nextInt();
      a[u].add(v);
      a[v].add(u);
    }

LinkedList (java.util.LinkedList< E>)

• 이중 연결 리스트
• java.lang.Object
  - java.util.AbstractCollection< E>
  - java.util.AbstractList< E>
  - java.util.AbstractSequentialList< E>
  - java.util.LinkedList< E>
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
• C++에서 List와 같은 역할
• 실제 프로그래밍 대회에서는 많이 쓰이지 않는다.

Stack (java.util.Stack< E>)

• 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조
• 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO)라고도 한다.
• E push(E item)
  - push: 스택에 자료를 넣는 연산
• E pop()
  - pop: 스택에서 자료를 빼는 연산
• E peek()
  - top: 스택의 가장 위에 있는 자료를 보는 연산
• bool empty()
  - empty: 스택이 비어있는지 아닌지를 알아보는 연산
• int size()
  - size: 스택에 저장되어 있는 자료의 개수를 알아보는 연산
• C++의 Stack과의 가장 큰 차이점은 Return 값의 유무
  - Java는 리턴 값이 있음
  • C++은 리턴 값이 없음
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

Set (java.util.Set< E>)

• 인터페이스이다.
• 중복된 원소를 포함하지 않는다.
• Set을 구현한 라이브러리
  - HashSet
  • TreeSet
  • LinkedHashSet
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/Set.html
• Set의 기본 메소드
  - boolean add(E e)
  • void clear()
  • boolean contains(Object o)
  • boolean isEmpty()
  • boolean remove(Object o)
  • int size()
  • Object[] toArray()
    • STL의 경우 시간 복잡도가 모두 log(n)으로 고정
      • Java의 경우 어떻게 구현된 것을 사용하냐에 따라 시간 복잡도가 변화

HashSet (java.util.HashSet< E>)

• java.lang.Object
  - java.util.AbstractCollection< E>
  - java.util.AbstractSet< E>
  - java.util.HashSet< E>
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
• HashTable을 이용해서 구현
• 삽입/삭제/제거 연산의 시간 복잡도가 O(1)이다.
• 순서가 보장되지 않는다.
  - 집합이 필요한데 순서가 보장될 필요가 없는 경우에 사용

	import java.util.*;
	public class Main {
      public static void main(String args[]) {
      	HashSet<Integer> d = new HashSet<integer>();
        for (int i=10; i>=1; i--) {
          d.add(i); 
        }
        for (int x : d) {
          System.out.println(x + " "); // 순서대로 출력이 보장되지 않는다.
        }
      }
    }

TreeSet (java.util.TreeSet< E>)

• java.lang.Object
  - java.util.AbstractCollection< E>
  - java.util.AbstractSet< E>
  - java.util.TreeSet< E>
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html
• STL의 Set과 거의 같은 역할
• 이진 검색 트리 (레드 블랙 트리)를 이용해서 구현되어 있다.
• 삽입/삭제/제거 연산의 시간 복잡도가 O(lgN)이다.
• (오름차, 내림차) 순서가 보장된다.
  - 가장 큰 장점임
  • 넣는 순서가 아닌 Comparable에 따라 내림차, 오름차 등이 보장됨

	import java.util.*;
	public class Main {
      public static void main(String args[]) {
        TreeSet<Integer> d = new TreeSet<Integer>();
        for (int i=10; i>=1; i--) {
          d.add(i);  
        }
        for (int x : d) {
          System.out.println(x + " ");  
        }
      }
    }

LinkedHashSet (java.util.LinkedHashSet< E>)

• java.lang.Object
  - java.util.AbstractCollection< E>
  - java.util.AbstractSet< E>
  - java.util.LinkedHashSet< E>
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html
• 삽입/삭제/제거 연산의 시간 복잡도가 O(1)이다.
• 추가한 순서가 보장된다.

	import java.util.*;
	public class Main {
      public static void main(String args[]) {
        LinkedHashSet<Integer> d = new LinkedHashSet<Integer>();
        for (int i=10; i>=1; i--) {
          d.add(i);  
        }
        for (int x : d) {
          System.out.println(x + " ");  
        }
      }
    }

Set의 선택

• 일반적인 경우 HashSet
• (오름차, 내림차) 순서가 중요한 경우 TreeSet (line sweeping algorithm)
• 입력한 순서가 중요한 경우 LinkedHashSet
• Set의 예제
  - 숫자카드 문제 (https://www.acmicpc.net/problem/10815)
  - 순서가 중요하지 않다.
  - 즉, HashSet을 사용하는 것이 유리하다.
  - 각 구현 Set의 결과
  - HashSet: 764MS
  - TreeSet: 1028MS
  - LinkedHashSet: 832MS

Map

• Set과 같이 Interface임
• 중복된 Key를 포함하지 않는다.
• (Key, Value) 쌍을 이룬다. (사전과 비슷)
• Map을 구현한 것
  - HashMap
  • TreeMap
    • RedBlack Tree를 이용
  • LinkedHashMap
• 주요 Method
  - void clear()
  - Map을 초기화
  • boolean containsKey(Object key)
    • 어떠한 Key가 들어있는지 확인
  • boolean containsValue(Object value)
    • 어떠한 Value를 가지고 있는지 확인
  • Set<Map.Entry<K,V>> entrySet()
    • Key, Value 쌍을 이용한 Set을 생성
  • V get(Object key)
    • Key에 해당하는 Value Return
  • boolean isEmpty()
    • 비어있는지 확인
  • Set< K> key keySet()
    • Key를 이용해 Set을 만들어줌
  • V put(K key, V value)
    • Key, Value 쌍을 넣을 수 있음
  • boolean remove(Object o)
    • 해당하는 Key를 Remove
  • int size()
    • Size Return
• 사용 예
  - 듣도보도 못한 사람 찾기 (https://www.acmicpc.net/problem/1764)
  • TreeMap을 이용한 풀이

    		```Java
    		import java.io.BufferedReader;

    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.*;
    public class Main {
    public static void main(String args[]) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] line = br.readLine().split(" ");
    int n = Integer.parseInt(line[0]);
    int m = Integer.parseInt(line[1]);
    TreeMap<String, Integer> d = new TreeMap<String, Integer>();
    for (int i=0; i<n; i++) { // 듣도 못한 사람 추가
    String name = br.readLine();
    d.put(name, 1);
    }
    for (int i=0; i<m; i++) { // 보도 못한 사람 + 2
    // 이미 듣도 못한 사람이었으면 3
    String name = br.readLine();
    Integer v = d.get(name);
    if (v == null) {
    v = 0;
    }
    v += 2;
    d.put(name, v);
    }
    ArrayList a = new ArrayList();
    for (Map.Entry<String, Integer> entry : d.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    if (value == 3) {
    a.add(key);
    }
    }
    System.out.println(a.size());
    for (String name : a) {
    System.out.println(name);
    }
    }
    }

  • HashMap을 이용한 풀이

    			import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.*;
    public class Main {
        public static void main(String args[]) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int m = Integer.parseInt(line[1]);
            TreeMap<String, Integer> d = new HashMap<String, Integer>();
            for (int i=0; i<n; i++) { // 듣도 못한 사람 추가
                String name = br.readLine();
                d.put(name, 1);
            }
            for (int i=0; i<m; i++) { // 보도 못한 사람 + 2
              						  // 이미 듣도 못한 사람이었으면 3
                String name = br.readLine();
                Integer v = d.get(name);
                if (v == null) {
                    v = 0;
                }
                v += 2;
                d.put(name, v);
            }
            ArrayList<String> a = new ArrayList<String>();
            for (Map.Entry<String, Integer> entry : d.entrySet()) {
                String key = entry.getKey();
                Integer value = entry.getValue();
                if (value == 3) {
                    a.add(key);
                }
            }
            System.out.println(a.size());
          	Collections.sort(a);
            for (String name : a) {
                System.out.println(name);
            }
        }
    }

  • 시간 복잡도를 잘 계산하여 효과적으로 하는 것이 좋다.
  • 계속 큰 시간복잡도를 가진 삽입을 사용하는 것이 나은가 vs 한번 정렬하는 시간복잡도를 사용하는 것이 나은가
  • 이 경우에는 HashSet이 대량의 데이터 삽입에 있어서 효율이 좋았던 것 같음았다
  • HashSet으로 Map을 만든 후에 한번 정렬해주는 것이 더 좋았다

Queue

• Java에서 Queue는 Interface로 구현되어 있다.
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
• Queue를 구현한 클래스는 다음과 같다.
  - ArrayDeque
  • LinkedList
  • PriorityQueue
    • 위의 것과는 다른 방식의 큐이다.
      • 최대값 또는 최소값이 우선순위를 갖고 그것이 먼저 나오는 큐
• 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조
• 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 한다.
• 대표 메소드
  - push: boolean offer(E e)
  - 큐에 자료를 넣는 연산
  • pop: E poll()
    • 큐에서 자료를 빼는 연산
      • C++에서는 Return을 하지 않는다.
  • front: E peek()
    • 큐의 가장 앞에 있는 자료를 보는 연산
  • back: (java에는 존재하지 않는다.)
    • 큐의 가장 뒤에 있는 자료를 보는 연산
  • empty: boolean isEmpty()
    • 큐가 비어있는지 아닌지를 알아보는 연산
  • size: int size()
    • 큐에 저장되어 있는 자료의 개수를 알아보는 연산

PriorityQueue

• 크기가 가장 작거나 큰 것부터 pop이 되는 queue를 말한다.
• 최대 Heap이나 최소 Heap을 이용하여 구현하는 경우가 많다.
• java.lang.Object
  - java.util.AbstractCollection< E>
  - java.util.AbstractQueue< E>
  - java.util.PriorityQueue< E>
• 공식 문서
  - https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
• 예제
  - PriorityQueue를 이용한 최소 힙 문제의 구현

  		public class Main {
    public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      PriorityQueue<Integer> q = new PriorityQueue<Integer>();
      int n = sc.nextInt();
      while (n-- > 0) {
        int x = sc.nextInt();
        if(x == 0) {
          if(q.isEmpty()) {
            System.out.println(0); 
          } else {
            System.out.println(q.poll()); 
          }
        } else {
          q.offer(x); 
        }
      }
    }
  }

  • PriorityQueue를 이용한 최대 힙 문제의 구현

    			public class Main {
      static class Compare implements Comparator<Integer> {
        public int compare(Integer one, Integer two) P
          return two.compareTo(one); 
        }
      }
      public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        Compare cmp = new Compare();
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(1, cmp);
        int n = sc.nextInt();
        while (n-- > 0) {
          int x = sc.nextInt();
          if(x == 0) {
            if(q.isEmpty()) {
              System.out.println(0); 
            } else {
              System.out.println(q.poll()); 
            }
          } else {
            q.offer(x); 
          }
        }
      }
    }