• ListIterator 인터페이스 활용하기 :: 마이구미
    Java 2016. 11. 21. 23:21
    반응형

    이번 글은 자바에서 활용할 수 있는 ListIterator 인터페이스를 다룰 것이다.

    처음보거나 사용해본 적이 없다면 굉장히 유용하게 사용할 수 있다.


    백준 알고리즘 사이트 1406번 문제 '에디터'를 접근하면서 알아보겠다.


    위 문제를 간략히 살펴보면, 인덱스를 임의대로 이동하면서 삽입 및 수정 등을 처리하는 문제이다.

    단순히 생각해보자. ArrayList를 쓸까?  LinkedList를 쓸까?

    삽입과 수정을 자유자재로 한다? 이렇게 해석이 가능했다면, 아마 LinkedList를 떠올렸을 거라 생각한다.


    잠깐 ArrayList와 LinkedList에 대해 짚고 넘어가자.


    linkedlist vs arraylist



    ArrayList의 경우는 데이터 삽입/삭제 시 임시 배열을 생성하여 데이터를 복사하는 방식으로 구현된다.

    그렇기에 데이터가 많을수록 성능이 저하된다.

    하지만 내부적으로 Array 기반이기 때문에 각 데이터에 인덱스를 가지기 때문에 검색에는 인덱스를 통해 접근하기 때문에 유리하다.


    LinkedList의 경우는 각 요소는 이전과 다음 요소의 정보를 가지고 있다는 점이 ArrayList와의 가장 큰 차이점이다.

    ArrayList와 같이 임시 배열을 생성할 필요 없이 이전과 다음 요소의 정보를 활용하여 삽입 및 삭제를 처리할 수 있기에 삽입/삭제가 유리하다.

    하지만 검색시에는 인덱스를 통해 접근하는 것이 아니기에 최악의 경우는 모든 요소를 다 살펴봐야하기 때문에 불리하다,


    문제의 경우는 데이터 삽입/삭제가 주요 기능이다.

    그렇기에 LinkedList를 통해 커서의 위치를 하나의 변수를 만들어 관리한다면 쉽게 풀 수 있다.

    예를 한번 보자.

    if (command.equals("L")) { if(cursor != 0) { cursor--; } } else if (command.equals("D")) { if(cursor != list.size()) { cursor++; } } else if (command.equals("B")) { if (cursor == 0) { continue; } list.remove(--cursor); } else { list.add(cursor,sc.next().charAt(0)); cursor++; }

    위와 같은 방법으로 위치 인덱스를 하나의 변수를 통해 관리하면 된다.

    사실 상 LinkedList만을 활용해도 충분히 문제를 해결하는데는 어려움이 없다.

    하지만 여기서 단점이 존재한다. 무엇일까?

    그것은 위에서 언급한 LinkedList의 특징에 있다.

    삽입/삭제 시 이전 요소와 다음 요소의 정보를 가지고 있는 것이 유리한점으로 언급했었다.

    하지만 결국 ArrayList와 상대적으로 유리한 것이다.

    결국 삽입/삭제 시 그 인덱스에 바로 접근하는 것이 아니다.

    head와 tail을 제외하고는 하나하나 살펴보면서 찾아가 처리하기 때문에 완전히 효율적이라고는 볼 수 없다.


    그렇다면 여기서 무엇이 있었으면 좋겠는가?

    위치를 찾아가지 말고 문제의 커서처럼 해당하는 위치에 있으면서 삽입/삭제를 처리할 수 있기만 하면 된다.

    이때 활용할 수 있는 것이 ListIterator가 되겠다.


    ListIterator는 Iterator를 상속한 인터페이스다.

    Iterator의 단방향 탐색과 달리 양방향 탐색이 가능하다.

    그렇기에 이 문제처럼 양방향으로 이동하면서 수정하기에 효율적이다.

    메소드명만 보아도 이해하기 쉽다.


    listlterator method



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

    ListIterator iterator = list.listIterator(list.size());


    크게 어려울 게 없으니 바로 문제를 풀어보면서 이해하는 것이 좋을 것이다.

    그 후 ListIterator를 이용하여 아래 문제 또한 풀어보아라.

    전체 소스는 Github URL을 통해 확인하길바란다.


    백준 알고리즘 문제 1406번 에디터 전체 소스

    https://github.com/hotehrud/acmicpc/blob/master/list/1406.java


    백준 알고리즘 문제 5397번 키로거

    https://www.acmicpc.net/problem/5397




    반응형

    댓글 0

Designed by Tistory.