AOJ ALDS1_3_C 双方向連結リスト (Java11)

最終的な提出コード(AC)

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> list = new ArrayDeque<Integer>();
         String str = br.readLine();
        int n = Integer.parseInt(str);

        for (int i = 0; i < n; i++) {
            String tmp = br.readLine();
            if (tmp.equals("deleteFirst")) {
                list.pop();
            } else if (tmp.equals("deleteLast")) {
                list.removeLast();
            } else {
                String command = tmp.substring(0, tmp.indexOf(" "));
                int x = Integer.parseInt(tmp.substring(tmp.indexOf(" ")+1));
                if (command.equals("insert")) list.push(x);
                else if (command.equals("delete")) list.remove((Integer) x);
            }
        }
        Iterator iterator = list.iterator();
        int i = list.size();
        int j = 0;
        while (iterator.hasNext()) {
            if (j != i-1) {
                System.out.print(iterator.next());
                System.out.print(" ");
            } else {
                System.out.println(iterator.next());
            }
            j++;
        }
    }
}

自力で届いた回答

class Main {
    public static void main(String[] args)  throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        var list = new ArrayList<Integer>();
        String str = br.readLine();
        int n = Integer.parseInt(str);
        
        for (int i = 0; i < n; i++) {
            String tmp = br.readLine();
            if (tmp.equals("deleteFirst")) {
                list.remove(0);
            } else if (tmp.equals("deleteLast")) {
                list.remove(list.size()-1);
            } else {
                String command = tmp.substring(0, tmp.indexOf(" "));
                int x = Integer.parseInt(tmp.substring(tmp.indexOf(" ")+1));
                if (command.equals("insert")) list.add(0, x);
                else if (command.equals("delete")) list.remove((Integer) x);
            }
        }
        for (int i = 0; i < list.size(); i++) {
            if (i != list.size()-1) {
                System.out.print(list.get(i));
                System.out.print(" ");
            } else {
                System.out.println(list.get(i));
            }
        }
    }
}

• テストケース10でTLEになり通らず

---

元々は入力をScannerで受け取っていたが、
sc.next()
だと、空白を区切りと判断し文中の x を受け取れておらず
sc.nextLine()
で、一行受け取ってしまえば良かったと思った頃には後者のコードを記述済み

---

前者と後者で違いは、

• x をArrayDeque<>かArrayList<>に入れるか

• 使用するデータ構造に伴った関数の利用

テストケース１０はおそらく、全てのcommandがinsertであり、
ArrayDequeのpush(),addFirst()とArrayListのadd()に計算量の差があるとみる

• SE11のソースを読んでみたが、イマイチ理解に至らず