[240320] 알고리즘 리부트 34일차 - 백준 1406 자바

[Part1-Chapter09-Clip01]

Array: 동일한 타입의 여러 원소를 선형 집합으로 관리하는 정적인 데이터 구조를 말한다. 생성과 동시에 크기를 지정해야 하며 이는 고정되어 늘릴 수 없다. 메모리에 물리적 순서가 고정되어 있어 인덱스로 접근이 가능하다.

인덱스로 접근이 가능하므로 조회 및 변경은 속도가 빠르지만 맨 앞에 있거나 중간에 있는 원소의 삭제나 삽입은 해당 인덱스 뒤의 연속된 원소를 한 인덱스씩 뒤로 미루거나 앞으로 당겨야 하므로 이 경우 속도가 느리다.

List: 동일한 타입의 여러 원소를 선형 집합으로 관리하는 동적인 데이터 구조를 말한다. 원소가 추가/삭제 됨에 따라 크기 변경이 가능하다. 구현체는 ArrayList, LinkedList, Vector로 각 특성이 다른데 ArrayList는 배열의 특성을 닮아서 Array처럼 인덱스를 활용한 원소 접근은 빠르지만 삽입/삭제의 경우 느리다. LinkedList의 경우 삽입/삭제의 경우 해당하는 곳의 주소값만 변경해주면 되기 때문에 속도가 빠르다. 반면 인덱스 접근의 경우 선형 탐색이 필요하기 때문에 즉 참조값을 다 따라가야 하기 때문에 느린 편이다.

Vector는 내부 구현이 동기화되어 있기 때문에 멀티 스레드 환경에서 안전하게 사용 가능하나 비교적 속도가 느리다. 실제 개발 환경에서는 여러 스레드가 리스트에 접근하게 되면 문제가 발생하기 때문에 외부에서 동기화를 제공하거나 Vector를 활용하는 게 좋다. 하지만 Collection 프레임워크 나오기 전에 구현된 자료구조라서 시간이나 메모리 효율은 이후에 나온 ArrayList가 좋은 편이다.

 

[Part1-Chapter09-Clip03]

이 강의에서는 iterator의 사용법에 대해 설명하고 있어 그 부분을 기록하고자 한다. 직접 LinkedList를 구현해서 다음 노드를 참조할 수 있도록 접근자를 만들어둔다면 상관없지만.. 만약 라이브러리에서 제공하는 LinkedList를 사용하고자 한다면 노드들에 순차 접근하기 위해 ListIterator를 반드시 사용해야 한다. iterator를 쓰는 이유는 get, set, remove을 빨리 수행하기 위

매서드들은 다음과 같다. 3번 및 4번의 기능은 기본 iterator와 달리 앞쪽으로도 이동할 수 있다는 특징을 보여준다.

1. hasNext(): 현재 커서 위치 뒤에 다음 노드가 있는지 논리값으로 반환 => 이동 가능한 상태인지 확인 역할
2. next(): 현재 커서 위치 뒤 노드를 넘어서 커서 이동 후 가리키는 건 이동 후 커서 바로 앞 원소 (직전에 참조한 값) 
3. hasPrevious(): 현재 커서 위치 앞에 이전 노드가 있는지 논리값으로 반환  => 이동 가능한 상태인지 확인 역할
4. previous(): 현재 커서 위치 앞 노드를 넘어서 커서 이동 후 가리키는 건 이동 후 커서 바로 뒤 원소 (직전에 참조한 값) 
5. nextIndex(): 다음 노드의 인덱스
6. previousIndex(): 이전 노드의 인덱스
7. remove(): 직전에 참조한 값(lastReturned)을 저장하고 있어서 삭제하면 직전에 참조한 값을 삭제한다. 주의할 점은 삭제함과 동시에 참조하고 있던 노드와 값을 모두 지우기 때문에 previous()나 next()로 통해 커서(iterator)를 이동하기 전 이 매서드를 사용하면 예외가 발생한다. 또한 직전의 메서드가 previous()였는지 next()였는지에 따라 지워지는 값이 바뀌기 때문에 이 또한 주의해야 한다.
8. set(E e): 직전에 참조한 값 (lastReturned) 을 저장하고 있어서 set하면 직전에 참조한 값의 위치에 원소를 저장한다.(바꾼다는 말) 주의할 점은 값을 갱신함과 동시에 참조하고 있던 노드와 값을 모두 지우기 때문에 previous()나 next()로 통해 커서(iterator)를 이동하기 전 이 매서드를 사용하면 예외가 발생한다. 또한 직전의 메서드가 previous()였는지 next()였는지에 따라 갱신되는 값이 바뀌기 때문에 이 또한 주의해야 한다.
9. add(E e): 현재 커서가 가리키는 위치에 새로운 요소를 추가하고 커서는 추가된 요소 뒤에 위치하게 된다.

ListIterator 생성 시 인덱스로부터 커서의 위치 조정 가능

 

[Part1-Chapter09-Clip04]

- 백준 1406 에디터

import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String originStr = sc.next();

        LinkedList<Character> list = new LinkedList<>();

        for (int i = 0; i < originStr.length(); i++) {
            list.add(originStr.charAt(i));
        }

        ListIterator<Character> iterator = list.listIterator();

        // 초기의 커서는 리스트의 제일 앞에 있음

        // 맨 뒤에 커서가 있다고 하니까!
        while (iterator.hasNext()) {
            iterator.next();
        }
        // 위 방식 대신 선언할 때 아예 위치를 맨 뒤로 옮겨놓고 시작할 수도 있음
        // ListIterator<Character> iterator = list.listIterator(originStr.length());

        int commNum = sc.nextInt();

        while (commNum-- > 0) {
            String comm = sc.next();

            switch (comm) {
                case "L":
                    if (iterator.hasPrevious()) iterator.previous();
                    //System.out.println(list);
                    break;
                case "D":
                    if (iterator.hasNext()) iterator.next();
                    //System.out.println(list);
                    break;
                case "B":
                    if (iterator.hasPrevious()) {
                        iterator.previous();
                        iterator.remove();
                        // remove 연산은 직전에 참조했던 값을 지우기 때문에 우리가 원하는 값을
                        // 지우기 위해서는 앞으로 한 칸 이동한다면 이제 참조하는 값이 우리가 처리하고자 하는 값이 된다.
                    }
                    //System.out.println(list);
                    break;
                case "P":
                    String letter = sc.next();
                    iterator.add(letter.charAt(0)); // next 앞에 새 노드를 연결 next가 없으면 previous 뒤쪽에 연결
                    //System.out.println(list);
                    break;
            }

        }
        StringBuilder sb = new StringBuilder();

        for (char c : list) {
            sb.append(c);
        }

        System.out.println(sb.toString());


    }
}