[JAVA] 백준 5397. 키로거(시뮬레이션, ListIterator) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 시뮬레이션을 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

사진을 클릭하면 문제 페이지로 이동합니다

 

2. 입출력 예제

 

3. 접근

 문제를 접하는 순간 문자열을 순회하면서 '<', '>', '-' 인 경우 따로 처리하고, 이 외의 경우에는 문자를 추가하는 방식으로 풀려고 했습니다. 하지만 LinkedList.add()나 remove() 메소드의 시간 복잡도가 문제가 되었습니다. 길이가 1,000,000이 되는 문자열의 각 문자를 add/remove하기엔 시간이 너무나도 오래 걸렸습니다. 때문에 Stack을 사용해도 되지만 저는 ListIterator 인터페이스를 사용하여 시간을 단축했습니다.

 

ListIterator<E> 인터페이스

 ListIterator 인터페이스는 Iterator인터페이스를 상속받아 여러 기능을 추가한 List에서 제공하는 인터페이스입니다.

Iterator 인터페이스는 한 방향으로만 이동할 수 있습니다. 하지만 ListIterator 인터페이스는 양방향으로 탐색하면서 추가/삭제/검색을 위한 기능을 제공하고 있습니다.

주의할 점은 ListIterator 인터페이스는 List 인터페이스를 구현한 인스턴스에서 listIterator() 메소드를 통해서만 구현할 수 있습니다.

메소드	설명
void add(E e)	리스트의 nextIndex() 위치에 e를 추가함.
boolean hasNext()	리스트에 다음 데이터가 존재하면 true 반환, 그렇지 않은 경우 false 반환
boolean hasPrevious()	리스트에 이전 데이터가 존재하면 true 반환, 그렇지 않은 경우 false 반환
E next()	리스트의 다음 데이터를 반환, 리스트 내 커서 위치를 다음 방향으로 이동
E previous()	리스트의 이전 데이터를 반환, 리스트 내 커서 위치를 이전 방향으로 이동
int nextIndex()	현재 커서 기준으로 다음 index 반환 (초기값 0)
int previousIndex()	현재 커서 기준으로 이전 index 반환 (초기값 -1)
void remove()	next(), previous()로 반환된 가장 최근 데이터를 리스트에서 삭제
void set(E e)	next(), previous()로 반환된 가장 최근 데이터를 e로 대체

쉽게 생각하면 타자를 칠 때, 커서 위치를 기준으로 생각하면 됩니다.

약간의 예시를 보여드리겠습니다.

 

""

nextIndex() = 0, previousIndex() = -1

add('A')

"A"

nextIndex() = 1, previousIndex() = 0

add('B')

"AB"

nextIndex() = 2, previousIndex() = 1

add('C')

"ABC"

nextIndex() = 3, previousIndex() = 2

previous();

previous();

(커서가 C뒤에서 A뒤로 이동 ; 이전 방향으로 두 번 이동했기 때문)

"ABC"

nextIndex() = 1, previousIndex() = 0

add('D')

"ADBC"

nextIndex() = 2, previousIndex() = 1

 

위처럼 동작하게 됩니다.

 

4. 로직

 로직 자체가 까다롭거나 어려운 문제는 아닙니다. 받은 문자열을 0부터 끝가지 순회하면서 어떤 문자냐에 따라서 ListIterator 인터페이스의 메소드를 적절하게 사용한다면 간단한 문제입니다.

1. '<' 인 경우, 이전 데이터가 존재할 때, 커서를 이전 방향으로 이동

2. '>' 인 경우, 다음 데이터가 존재할 때, 커서를 다음 방향으로 이동

3. '-' 인 경우, 이전 데이터가 존재할 때, 커서를 이전 방향으로 이동한 뒤 삭제

4. 1,2,3의 경우가 아닌 경우, 문자를 add()

 

5. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.ListIterator;
 
public class Main {
    static LinkedList<Character> lnklist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int TC = Integer.parseInt(br.readLine());
        for(int i = 0; i < TC; i++) {
            lnklist = new LinkedList<>();
            ListIterator<Character> list = lnklist.listIterator();
            String str = br.readLine();
            
            for(int j = 0; j < str.length(); j++) {
                char c = str.charAt(j);
                switch(c) {
                    case '<' :
                        if(list.hasPrevious()) {
                            list.previous();
                        }
                        break;
                    case '>' :
                        if(list.hasNext()) {
                            list.next();
                        }
                        break;
                    case '-' :
                        if(list.hasPrevious()) {
                            list.previous();
                            list.remove();
                        }
                        break;
                    default : 
                        list.add(c);
                }
            }
            
            StringBuilder sb = new StringBuilder();
            for(char s : lnklist) {
                sb.append(s);
            }
            System.out.println(sb.toString());
        }
    }
}
 

 

6. 결과

ListIterator 인터페이스 사용

ListIterator 인터페이스 미사용