자료구조

---

알고리즘 문제풀이에 자주 등장하는 자료구조에 대해서 알아보자!

Stack

LIFO (Last In, First Out), 중복 요소를 허용하는 특징을 가진 자료구조로 DFS 문제를 풀 때 주로 사용한다.

public static void main(String[] args) {  
    Stack<Integer> stack = new Stack<>();  
      
    //요소 삽입  
    stack.push(1);  
    stack.push(2);  
      
    //Stack이 비어있는지 확인  
    if (stack.empty()) System.out.println("Stack is Empty");  
      
    int lastItem = 0;  
      
    //최상단 요소 확인  
    if (stack.peek() == 2)  
        //최상단 요소 제거  
        lastItem = stack.pop();  
      
    //요소 찾기  
    if (stack.search(2) ** -1) System.out.println("2 is not Exist");  
}

Map

Key, Value로 데이터를 관리하는 자료구조로 키값은 중복이 불가능하다는 특징이 있다. Map을 탐색하는 시간 복잡도는 키값만 가지고 바로 접근이 가능하기 때문에 **O(1)== 이다.

public static void main(String[] args) {  
    HashMap<String, String> map = new HashMap<>();  
  
    //put item  
    map.put("key1", "value1");  
    map.put("key2", "value2");  
    map.put("key3", "a1");  
  
    //key,value 존재 여부 확인  
    if(map.containsKey("key1") && map.containsValue("value1"))  
        System.out.println("item exist!");  
  
    //key 값을 가져오며, 값이 없을 경우 기본값 설정  
    map.put("key1", map.getOrDefault(("key1"), "emptyValue") + " value changed");  
  
    //key Collection 가져오기  
    List<String> keyList = new ArrayList<>(map.keySet());  
  
    // value 값의 사전순으로 요소 정렬  
    Collections.sort(keyList, new Comparator<String>(){  
        public int compare(String s1, String s2){  
            String v1 = map.get(s1);  
            String v2 = map.get(s2);  
  
            return v1.compareTo(v2);  
        }  
    });  
  
    //map의 크기  
    System.out.println(map.size());  
}

Set

집합 개념의 자료구조로 중복을 허용하지 않는 특징이 있다. Set의 한 종류인 TreeSet은 정렬되어 저장되며, HashSet은 정렬 되지 않은 상태로 저장된다.

public static void main(String[] args) {  
    //{tom, john}  
    TreeSet<String> treeSet = new TreeSet<>();  
  
    treeSet.add("tom");  
    treeSet.add("tom");  
    treeSet.add("john");  
  
    //{john, tom}  
    HashSet<String> hashSet = new HashSet<>(treeSet);  
  
    // 요소 접근을 위해 Iterator 사용  
    Iterator<String> iterator = hashSet.iterator();  
    while (iterator.hasNext()) {  
        String element = iterator.next();  
        if (element.length() % 2 == 0) {  
            //요소 제거  
            iterator.remove();  
        }  
    }  
}

---

연결문서