백준 5430 AC with 자바

---

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

풀이

더블리 링크드 리스트를 학습하기 아주 좋은 예제이다

진짜 그냥 더블리 링크드 리스트 구현해서 풀면 된다

 

링크드 리스트에 사용할 노드 클래스를 구현해주고

private static class Node {
    int n;
    Node pre;
    Node next;

    public Node(int n) {
        this.n = n;
    }
}

 

head와 tail을 선언하고

head와 tail 중 어떤 노드를 가리키는지 표시할 current와

아무것도 없는데 D를 한 경우를 확인하기 위한 에러 플래그를 선언해준다

static Node head;
static Node tail;
static Node current;
static Boolean flag;

 

숫자 차례대로 받으면서 링크드 리스트에 넣어주고

숫자를 다 받으면 current는 head를 가리켜 준다

for (int i = 0; i < N; i++) {
    int n = Integer.parseInt(st.nextToken());
    Node newNode = new Node(n);

    if (head == null) {
        head = newNode;
    } else {
        tail.next = newNode;
        newNode.pre = tail;
    }
    tail = newNode;
}

current = head;

 

"R"인 경우

current가 가리키는 값을 토글 해준다

if (current == head) current = tail;
else if (current == tail) current = head;

 

"D"인 경우

먼저, 저장되어 있는 숫자가 없는 경우 flag를 활성시켜 준다

if (head == null) {
    flag = true;
    break;
}

 

그다음, current가 어느 것을 가리키냐에 따라 분기 처리해준다

 

current가 head를 가리키는 경우,

current와 head를 다음 노드로 갱신해주고

갱신된 head의 이전 노드를 삭제해준다

if (current == head) {
    current = head.next;
    head = head.next;
    if (head != null) head.pre = null;
}

 

current가 tail를 가리키는 경우,

current와 tail를 이전 노드로 갱신해주고

갱신된 tail의 다음 노드를 삭제해준다

else if (current == tail) {
    current = tail.pre;
    tail = tail.pre;
    if (tail != null) tail.next = null;
}

 

R, D 처리가 끝나면 flag를 체크해주고

flag가 활성화된 경우, error를 출력해준다

if (flag) {
    bw.write("error\n");
    continue;
}

 

또, current가 어느 것을 가리키냐에 따라 분기 처리해주며 답을 출력해준다

 

current가 head를 가리키는 경우,

head에서부터 다음 노드로 가며 숫자를 출력해준다

if (current == head) {
    if (head == null) bw.write("[]");
    else {
        bw.write("[");
        while (head.next != null) {
            bw.write(head.n + ",");
            head = head.next;
        }
        bw.write(head.n + "]");
    }
}

 

current가 tail을 가리키는 경우,

tail에서부터 이전 노드로 가며 숫자를 출력해준다

else if (current == tail) {
    if (tail == null) bw.write("[]");
    else {
        bw.write("[");
        while (tail.pre != null) {
            bw.write(tail.n + ",");
            tail = tail.pre;
        }
        bw.write(tail.n + "]");
    }
}

 

---

 

전체 코드

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

public class Main {

    static Node head;
    static Node tail;
    static Node current;
    static Boolean flag;

    private static class Node {
        int n;
        Node pre;
        Node next;

        public Node(int n) {
            this.n = n;
        }
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            String fun = br.readLine();
            int N = Integer.parseInt(br.readLine());

            head = null;
            tail = null;
            current = null;
            flag = false;

            String s = br.readLine();
            s = s.substring(1, s.length() - 1);
            StringTokenizer st = new StringTokenizer(s, ",");

            for (int i = 0; i < N; i++) {
                int n = Integer.parseInt(st.nextToken());
                Node newNode = new Node(n);

                if (head == null) {
                    head = newNode;
                } else {
                    tail.next = newNode;
                    newNode.pre = tail;
                }
                tail = newNode;
            }

            current = head;

            for (int i = 0; i < fun.length(); i++) {
                char c = fun.charAt(i);

                if (c == 'R') {
                    if (current == head) current = tail;
                    else if (current == tail) current = head;
                } else {
                    if (head == null) {
                        flag = true;
                        break;
                    }

                    if (current == head) {
                        current = head.next;
                        head = head.next;
                        if (head != null) head.pre = null;
                    } else if (current == tail) {
                        current = tail.pre;
                        tail = tail.pre;
                        if (tail != null) tail.next = null;
                    }
                }
            }

            if (flag) {
                bw.write("error\n");
                continue;
            }

            if (current == head) {
                if (head == null) bw.write("[]");
                else {
                    bw.write("[");
                    while (head.next != null) {
                        bw.write(head.n + ",");
                        head = head.next;
                    }
                    bw.write(head.n + "]");
                }
            } else if (current == tail) {
                if (tail == null) bw.write("[]");
                else {
                    bw.write("[");
                    while (tail.pre != null) {
                        bw.write(tail.n + ",");
                        tail = tail.pre;
                    }
                    bw.write(tail.n + "]");
                }
            }
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}