[알고리즘] 암호문3

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        for (int testCase = 1; testCase <= 10; testCase++) {
            int N = Integer.parseInt(br.readLine());
            LinkedList linkedList = new LinkedList();
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                linkedList.addLast(Integer.parseInt(st.nextToken()));
            }
            // 디버깅용
//            linkedList.add(6, 1);
//            linkedList.addLast(7);
//            linkedList.poll(1, 2);
//            linkedList.removeFirst()
//            for (int i = 0; i < N; i++) {
//                System.out.println(linkedList.removeFirst());
//
//            }
//            return;

            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                String token = st.nextToken();
                int x = 0;
                int y = 0;
                switch (token) {
                    case "I":
                        x = Integer.parseInt(st.nextToken());
                        y = Integer.parseInt(st.nextToken());
                        for (int i = 0; i < y; i++) {
                            linkedList.add(Integer.parseInt(st.nextToken()), x + i);
                        }
                        break;
                    case "D":
                        x = Integer.parseInt(st.nextToken());
                        y = Integer.parseInt(st.nextToken());
                        linkedList.poll(x, y);
                        break;
                    case "A":
                        y = Integer.parseInt(st.nextToken());
                        for (int i = 0; i < y; i++) {
                            linkedList.addLast(Integer.parseInt(st.nextToken()));
                        }
                        break;
                }
            }
            sb.append("#").append(testCase).append(" ");
            for (int i = 0; i < 10; i++) {
                sb.append(linkedList.removeFirst()).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    static class Node {

        int code;
        Node nextNode;

        public Node() {
        }

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

        public Node(int code, Node nextNode) {
            this.code = code;
            this.nextNode = nextNode;
        }
    }

    static class LinkedList {

        final Node head;
        final Node tail;

        public LinkedList() {
            head = new Node();
            tail = new Node();
            head.nextNode = tail;
            tail.nextNode = head;
        }

        public void add(int code, int x) {
            Node node = new Node(code);
            Node curNode = head;
            for (int i = 0; i < x; i++) {
                curNode = curNode.nextNode;
            }
            Node nextNode = curNode.nextNode;
            curNode.nextNode = node;
            node.nextNode = nextNode;
        }

        public void addLast(int code) {
            Node node = new Node(code);
            Node prevNode = tail.nextNode;
            prevNode.nextNode = node;
            tail.nextNode = node;
        }

        public void poll(int x, int y) {
            Node curNode = head;
            for (int i = 0; i < x; i++) {
                curNode = curNode.nextNode;
            }
            Node finalNode = curNode;
            for (int i = 0; i < y + 1; i++) {
                finalNode = finalNode.nextNode;
            }
            curNode.nextNode = finalNode;
        }

        public int removeFirst() {
            Node curNode = head;
            Node removeNode = curNode.nextNode;
            curNode.nextNode = removeNode.nextNode;
            return removeNode.code;
        }


    }
}

나의 풀이

- 특정 위치에 삽입하기 위해 LinkedList를 새로 만들었다.

- 디버깅이 어려웠다.

- LinkedList의 구현에는 큰 문제가 없었는데 switch에서 "D"에 y를 for문으로 돌아서 오류가 있었다. 

 

- 아래는 x부터 y개를 add하는 오퍼레이션에서 O(x+y)만 걸리도록 하였다. 위의 코드는 O(y(x+y))이 걸리도록 작성하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int testCase = 1; testCase <= 10; testCase++) {
            LinkedList linkedList = new LinkedList();
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                linkedList.addLast(Integer.parseInt(st.nextToken()));
            }

            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                int x = 0;
                int y = 0;
                switch (st.nextToken()) {
                    case "I":
                        x = Integer.parseInt(st.nextToken());
                        y = Integer.parseInt(st.nextToken());
                        linkedList.add(x, y);
                        break;
                    case "D":
                        x = Integer.parseInt(st.nextToken());
                        y = Integer.parseInt(st.nextToken());
                        linkedList.remove(x, y);
                        break;
                    case "A":
                        y = Integer.parseInt(st.nextToken());
                        for (int j = 0; j < y; j++) {
                            linkedList.addLast(Integer.parseInt(st.nextToken()));
                        }
                        break;
                }
            }

            sb.append("#").append(testCase).append(" ");
            linkedList.search();
        }
        System.out.println(sb);
    }

    static class Node {

        int code;
        Node nextNode;

        public Node() {
        }

        public Node(int code) {
            this(code, null);
        }

        public Node(int code, Node nextNode) {
            this.code = code;
            this.nextNode = nextNode;
        }
    }

    static class LinkedList {

        Node head;
        Node tail;

        public LinkedList() {
            this.head = new Node();
            this.tail = new Node();
            head.nextNode = tail;
            tail.nextNode = head;
        }

        public void addLast(int code) {
            Node newNode = new Node(code);
            Node lastNode = tail.nextNode;
            lastNode.nextNode = newNode;
            tail.nextNode = newNode;
        }

        public void add(int x, int y) {
            Node curNode = head;
            for (int i = 0; i < x; i++) {
                curNode = curNode.nextNode;
            }
            for (int i = 0; i < y; i++) {
                if (curNode.nextNode == null) {
                    addLast(Integer.parseInt(st.nextToken()));
                    curNode = curNode.nextNode;
                    continue;
                }
                Node newNode = new Node(Integer.parseInt(st.nextToken()));
                newNode.nextNode = curNode.nextNode;
                curNode.nextNode = newNode;
                curNode = curNode.nextNode;
            }
        }

        public void remove(int x, int y) {
            Node curNode = head;
            for (int i = 0; i < x; i++) {
                curNode = curNode.nextNode;
            }
            Node anchorNode = curNode;
            for (int i = 0; i < y; i++) {
                curNode = curNode.nextNode;
                if (curNode.nextNode == null) {
                    tail.nextNode = anchorNode;
                }
            }
            anchorNode.nextNode = curNode.nextNode;
        }

        public void search() {
            Node curNode = head;
            for (int i = 0; i < 10; i++) {
                if (curNode.nextNode == null) {
                    sb.append(-1);
                    break;
                }
                curNode = curNode.nextNode;
                sb.append(curNode.code).append(" ");
            }
            sb.append("\n");
        }
    }
}