[S2] 백준 5397번 키로거 Java 연결 리스트

리뷰

 

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

Java에서 연결 리스트를 활용할 수 있는 방법을 알게 되었다.

 

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. T에 테스트 케이스의 개수를 입력 받고, T번의 while루프를 수행해 준다.
2. 매 루프마다 연결 리스트 list를 초기화 하고, 리스트 이터레이터 it을 list의 반복자로 사용해 준다.
3. 변수 s에 문자열을 입력 받고, s문자열을 순회하는 for문을 개행해 준다.
4. 변수 c에 현재 인덱스에 해당하는 문자를 저장해 준다.
5. c가 '<'일 경우, it의 이전 요소가 있다면 해당 요소로 이동해 준다.
6. c가 '>'일 경우, it의 다음 요소가 있다면 해당 요소로 이동해 준다.
7. c가 '-'일 경우, it의 왼쪽 요소가 있다면 왼쪽으로 이동 후 해당 요소를 remove해준다.
8. 위에 해당되지 않을 경우 it에 c를 add해준다.
9. for문이 종료된 후 list에 남아있는 문자들을 출력하고 줄바꿈을 수행해 준다.

 

트러블 슈팅

1. 현재 위치를 정수형 변수 idx로, 연결 리스트를 LinkedList 하나만 사용하였더니 시간 초과가 발생하였다.
2. listIterator를 통해 현재 노드 정보를 관리하여 AC를 받았다.

 

참고 사항

1. 인덱스를 사용하는 것은 연결리스트에서 별 다른 도움이 되지 않는다.
2. listIterator를 통해 현재 노드 정보를 추적 관리할 수 있었다.

 

정답 코드

import java.util.*;
import java.io.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while (T-- > 0) {
            LinkedList<Character> list = new LinkedList<>();
            ListIterator<Character> it = list.listIterator();
            String s = br.readLine();
            
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '<') {
                    if (it.hasPrevious()) it.previous();
                }
                else if (c == '>') {
                    if (it.hasNext()) it.next();
                }
                else if (c == '-') {
                    if (it.hasPrevious()) {
                        it.previous();
                        it.remove();
                    }
                }
                else {
                    it.add(c);
                }
//                bw.write(c + " " + idx + "\n");
//                bw.flush();
            }
            for (Character c : list) {
                bw.write(c);
            }
            bw.write("\n");
        }

        br.close();
        bw.close();
    }
}