들어가며

BOJ5397 키로거를 푸는데 시간 초과가 났다.
1. 스택 2개로 푸는 방법
2. 연결리스트로 푸는 방법
이렇게 두가지의 풀이법이 대표적이었는데, 2번 방법이 내가 기존에 푼 방식과 똑같았다.
하지만 나는 자료구조 선택과 리스트의 인덱스(cursor)를 직접 관리해서 시간초과가 난 것이다.

Java에서 요소를 관리해주는 iterator에 대해 알아보자

Iterator

요소들을 하나씩 차례대로 접근할 수 있게 하는 인터페이스.

• 모든 컬렉션에 대한 표준화된 방법을 제공
• 단방향으로만 이동 가능 = 앞에서 뒤로만 순회 가능

주요 메서드

• hasNext(): 순회할 다음 요소가 있는지 여부를 반환
• next(): 다음 요소를 반환
• remove(): next()로 반환된 마지막 요소를 제거

ListIterator

Iterator의 기능을 확장한 인터페이스.

• ArrayList, LinkedList 와 같은 List 인터페이스를 구현한 컬렉션 클래스에서만 사용 가능.
• 양방향 순회 가능

주요 메서드

위의 세 메서드를 포함해 추가적인 기능 제공.

• hasPrevious(): 이전 요소를 가지고 있는지 여부를 반환
• previous() : 현재 위치에서 이전 요소로 이동하고, 그 요소를 반환.
  • 이전 요소 없을 시, NoSuchElementException 발생
  • 리스트를 역순으로 조회 가능
• add(E e) : 현재 위치 바로 앞에 지정된 요소 e를 리스트에 추가
  • 리스트의 구조를 변경하는 메서드
  • 메서드 호출 후, next(), previous() 를 호출해야, 추가적인 add, remove, set과 같은 값 갱신이 가능함.
• set(E e) : 마지막으로 반환된 요소를 지정된 요소 e로 대체
  • next(), previous() 호출 직후에만 유효하게 동작.
  • add(), remove() 메소드 호출 직후에는 set() 메소드를 호출할 수 없음.

출처 TCP School

BOJ5397.java

이제 연결리스트의 Iterator를 알았으니, 문제 풀이에 적용해보자.
백문 예제) 키로거

내가 처음에 시도했다가 시간초과난 코드를 보자.

시간초과 코드

	private static void solution(String input) {
        int cursor = 0;
        StringBuilder password = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            switch (c){
                case '-':
                    if(cursor == 0) continue;
                    password.delete(cursor-1, cursor);
                    cursor--;
                    break;
                case '<':
                    if(cursor > 0) cursor--;
                    break;
                case '>':
                    if(cursor < password.length()) cursor++;
                    break;
                default:
                    password.insert(cursor, c);
                    cursor++;
                    break;
            }
        }
        answer.append(password).append("\n");
    }

풀이 방법은 다음과 같다.

• password: 자료구조를 사용하지 않고 StringBuilder로 패스워드를 직접만드는 방식.
• cursor: 인덱스 관리변수를 두고, 이를 가지고 삽입, 삭제, 이동을 제어했다

이 풀이를 연결리스트를 사용해, ListIterator 를 사용해 커서를 관리하면 시간초과가 나지 않는다.

통과 코드

    private static void solution(String input) {
        List<Character> password = new LinkedList<>();
        ListIterator<Character> cursor = password.listIterator();

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            switch (c) {
                case '-':
                    if (!cursor.hasPrevious()) continue;
                    cursor.previous();      //이전 요소로 이동 후 반환
                    cursor.remove();        //반환된 마지막 요소를 제거함
                    break;
                case '<':
                    if (cursor.hasPrevious()) cursor.previous();
                    break;
                case '>':
                    if (cursor.hasNext()) cursor.next();
                    break;
                default:
                    cursor.add(c);      //현재 위치에 요소 추가
                    break;
            }
        }
        for(Character c : password) {
            answer.append(c);
        }
        answer.append("\n");
    }

위의 코드와 비교하면 구조가 똑같다는 것을 확인할 수 있다.

시간초과의 이유: 자료구조의 잘못된 선택

StringBuilder를 사용해 문자열을 처리하면 문자열을 사용할 때 내부적으로 배열을 사용한다.
이는 성능저하가 발생할 수 있음.

반면에 LinkedList와 ListIterator를 사용하면 포인터로 처리하게 되므로 작업 시간이 O(1)이다.

엥 그러면 자료구조만 List로 바꾸면 통과되나?

ㅇㅇ.. 처음에 StringBuilder로 선언한 password를
List<Character> password = new LinkedList<>();
이렇게 바꾸고 코드를 고치면 통과는 한다.
근데 시간이 2배 걸린다.

private static void solution(String input) {
        int cursor = 0;
        List<Character> password = new LinkedList<>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            switch (c) {
                case '-':
                    if (cursor == 0) continue;
                    password.remove(cursor - 1);
                    cursor--;
                    break;
                case '<':
                    if (cursor > 0) cursor--;
                    break;
                case '>':
                    if (cursor < password.size()) cursor++;
                    break;
                default:
                    password.add(cursor, c);
                    cursor++;
                    break;
            }
        }
        for(Character c : password) {
            answer.append(c);
        }
        answer.append("\n");
    }

의문점이 두 개가 생겼다.
1. 직접 cursor를 관리하는 것과 ListIterator의 시간 복잡도가 2배 차이나는 이유는?
2. 왜 ArrayList는 시간초과가 나고, LinkedList는 통과할 수 있나?

직접 cursor를 관리하는 것과 ListIterator의 시간 복잡도가 2배 차이나는 이유는?

ListIterator를 사용하여 순회하면, 현재 위치를 기억하고 있다.

ListIterator는 현재 노드의 참조를 유지하고 있어 바로 이전 노드나 다음 노드로의 접근 및 수정이 가능!
add() remove()와 같은 추가/삭제의 시간복잡도는 O(1)이다.

반면 직접 변수 cursor로 관리했을 때 add(cursor, c)와 remove(cursor - 1)와 같은 메서드를 수행하려면, 해당 인덱스까지 이동해야하기 때문에 시간복잡도가 O(n)이 걸린다.

왜 ArrayList는 시간초과가 나고, LinkedList는 통과할 수 있나?

둘 다 리스트 구현 방식이며, 관리 방식에 차이가 있다.

LinkedList

• 이중 연결 리스트. 각 요소는 자신의 데이터와 함께 이전 요소와 다음 요소를 가리키는 포인터를 가짐.
• 특정 요소를 추가/삭제 할 때 다른 요소를 이동시킬 필요 없이, 포인터만 변경하면 됨
  • 따라서 O(1)의 시간 복잡도를 가진다.
  • 단, 위치에 접근하는 데는 시간이 걸릴 수 있다.

ArrayList

• 동적 배열로 구현. 크기를 조정할 수 있는 배열을 사용해 요소 관리
• 인덱스를 통한 접근이 매우 빠름. O(1)
• 특정 위치에 요소를 추가/삭제 하는 경우, 모든 요소를 이동시켜야 함. O(n)

이런 특성으로 ArrayList로 구현했을 경우, 시간초과가 난다.

데이터의 삽입/삭제가 많은 경우, LinkedList가 더 빠르다.

마치며

시간초과가 발생하지 않도록, 적절한 자료구조를 찾는게 문제를 풀기 전 생각해봐야 하는 첫번째 문제인 것 같다.
하나씩 이동하는 것은 스택, 큐, 덱을 쓰는 것을 고민해보자.

그리고 Iterator는 처음 써봤는데, 인덱스를 기억하고 이를 관리할 때, List 자료구조를 쓴다면 떠올릴 줄 알기.

자료구조 선택 유의하기!

끝~