[코테 알고리즘] 컬렉션 프레임워크

본 글은 파이썬으로 코테를 준비하던 사람이 자바로 코테를 봐야해서 새로 공부할 때 정리한 내용입니다. 

 

 

컬렉션 프레임 워크

• 여러 개의 값을 저장하고, 그 값을 쉬우면서도 효율적으로 처리해주는 표준화 클래스
• 코테를 위한 다양한 자료구조가 포함됨
  • 리스트(ArrayList), 큐(Queue), 스택(Stack), 데크(ArrayDeque), 해시맵(Hashmap) 등

배열

• 기초 자료형으로서 저장할 데이터의 개수가 정해져있는 경우 사용
• 아래 코드는 배열의 동작 방식을 이해하기에 용이

package collections;

import java.util.Arrays;

public class ArraySolution {
    public static void main(String[] args) {
        int[] array1 = {1, 2, 3, 4, 5};
        int[] array2 = new int[]{1, 3, 5, 7, 9};

        int[] array3 = new int[5];
        array3[0] = 0;
        array3[1] = 2;
        array3[2] = 4;
        array3[3] = 6;
        array3[4] = 8;

        System.out.println(Arrays.toString(array1)); //[1, 2, 3, 4, 5]
        System.out.println(Arrays.toString(array2)); //[1, 3, 5, 7, 9]
        System.out.println(Arrays.toString(array3)); //[0, 2, 4, 6, 8]
    }
}

• Arrays 클래스의 toString() 메서드를 이용하면 배열 요소를 쉽게 출력

배열의 인덱스

• 인덱스 : 특정 원소 위치에 빠르게 접근하기 위한 기능
• 배열은 생성 이후에 크기를 조절할 수 없다는 것이 특징
  • 배열 생성 후 새 데이터를 삽입하거나 삭제 할수 없음
  • 기존 데이터의 변경만 가능
• 인덱스를 통한 배열 요소에 대한 접근 및 변경의 시간 복잡도는 O(1)

리스트

• 자바의 리스트는 주로 ArrayList를 이용함
• 배열은 크기가 고정되어 있지만, ArrayList는 가변 크기라는 것이 특징
  • 새 데이터를 삽입하거나 기존 데이터를 삭제할 수 있음
  • 단 시간복잡도가 최대 O(N)까지 커질 수 있다는 것이 단점
• 리스트 이해를 위한 코드

package collections;

import java.util.ArrayList;

public class ArrayListSolution {
    public static void main(String[] args) {
        // 리스트 객체 생성
        ArrayList<Integer> list = new ArrayList<>();

        // 리스트에 요소 추가
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        System.out.println(list.get(2)); // 3
        System.out.println(list); // [1, 2, 3, 4, 5]
    }
}

해시맵

• 해시맵은 키(key)와 값(value) 쌍을 저장하는 해시 테이블
• 키를 사용하여 값을 검색하는 자료구조
• 해시맵 이해를 위한 코드

package collections;

import java.util.HashMap;

public class HashMapSolution {
    public static void main(String[] args) {
        // 해시맵 초기화
        // 키로는 문자열을, 값은 정수형을 저장하는 해시맵
        HashMap<String, Integer> map = new HashMap<>();

        // 해시맵 값 삽입
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);
        System.out.println(map); // {one=1, two=2, three=3}

        // 해시맵 데이터 검색
        String key = "three";
        if (map.containsKey(key)) {
            System.out.println(key + " : " + map.get(key)); // three : 3
        } else {
            // 키가 해시맵에 없는 경우 예외처리
            System.out.println(key + "는 해시맵에 없습니다.");
        }

        // 해시맵 수정
        map.put("three", 33);
        System.out.println(map); // {one=1, two=2, three=33}

        // 해시맵 삭제
        map.remove("three");
        System.out.println(map); // {one=1, two=2}
    }
}

문자열

String

• 문자열은 이뮤터블 객체입니다.
  • 이뮤터블 객체 : 값을 변경할 수 없는 객체
  • 시간 복잡도 관점에서 사용 시 주의해야할 필요가 있음
• 문자열 추가나 삭제
  • 이뮤터블 객체는 객체를 수정하는 것이 아니라 새로운 객체를 반환하는 것

package collections;

public class StringSolution {
    public static void main(String[] args) {
        // 문자열 변수 선언
        String string = "Hello, World!";

        // 문자열 추가, 삭제
        // 기존 문자열이 아닌 새로운 문자열을 만들고 새로 참조하는 것
        String string2 = "He";
        string2 += "llo";
        System.out.println(string2); // Hello

        // 문자열 수정
        String string3 = "Hello, World!";
        // replace  첫 번째 인수에는 찾을 문자열을, 두 번째 인수에는 변경할 문자열을 입력
        string3 = string3.replace("World", "Java");
        System.out.println(string3); // Hello, Java!
    }
}

StringBuffer 와 StringBuilder

이뮤터블 객체

String s = "abc";
System.out.println(System.identityHashCode(s)); //168423058

s += "def";
System.out.println(System.identityHashCode(s)); // 1160460865
System.out.println(s); // abcdef

• String 객체는 값을 변경할 수 없는 Immutable 객체
• System.identityHashCode() 메서드
  • 객체를 특정할 수 있는 식별 값을 반환
  • 두 String을 합치면 새로운 객체로 변화되는 것을 확인
• 즉, String 객체의 값을 변경하는 작업은 새로운 String 객체를 만들고 값을 복사하는 작업을 수행
• 시간 복잡도
  • 문자열 길이가 N이라 가정하면 O(N)만큼 걸림

StringBuilder, StringBuffer

• 시간 복잡도 문제를 해결하고자 만들어짐
  • StringBuilder 클래스와 StringBuffer 클래스는 큐터블
  • 값을 변경할 때 시간복잡도 관점에서 더 효율적
• String을 변경하는 계산이 많은 경우 StringBuilder 클래스와 StringBuffer 클래스를 사용
• 둘의 차이는 멀티스레드 여부
  • 코테 환경에서는 관계가 없음
  • 코테의 경우 Thread-Safe가 없는 StringBuilder를 더 많이 사용

        // StringBuilder 객체 생성
        StringBuilder sb = new StringBuilder();
        
        // 문자열 추가
        sb.append("Hello");
        sb.append(", World!");
        
        // 문자열 출력
        System.out.println(sb.toString()); // Hello, World!
        sb.deleteCharAt(3); // 3번째 인덱스 문자 삭제
        System.out.println(sb.toString()); // Helo, World!
        sb.insert(3, "l"); // 3번째 인덱스에 문자열 추가
        System.out.println(sb.toString()); // Hello, World!