JAVA 백준 5430 AC (자료 구조)

백준 문제 풀이/백준 (JAVA)

JAVA 백준 5430 AC (자료 구조)

gamja00 2024. 7. 12. 19:00

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

문제

첫째 줄에 테스트 케이스 T( 1 <= T <= 100 ) 입력.
각 테스트 케이스 첫째 줄에 수행할 함수 p ( 1 <= p <= 100000 ) 입력.
배열에 들어있는 수의 개수 n ( 1 <= n <= 100000 )
[x,...,x] 형식으로 배열에 들어있는 정수 입력. x ( 1 <= x <= 100 )
2 ~ 4를 T번 반복함.
p의 길이의 합과 n의 합은 70만을 넘지 않는다.
수행할 함수는 AC언어를 사용. - R 입력시 배열을 reverse 하고 D 입력시 첫 번째 수를 삭제한다.
배열이 비어있을 때 D사용시 에러 발생. -> error 출력.
함수가 입력됐을 때 입력된 함수들을 순서대로 수행.
각 테스트 케이스에 대한 출력을 각 줄에 출력.

초기 코드

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

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

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

        for (int i = 0; i < N; i++) {
            boolean flag = true;

            String[] order = br.readLine().split("");

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

            ArrayList<String> list = new ArrayList<>(List.of(br.readLine().split(",")));

            list.set(0, list.get(0).replace("[", ""));
            list.set(list.size() - 1, list.get(list.size() - 1).replace("]", ""));

            for (int j = 0; j < order.length; j++) {
                if (list.isEmpty() && Objects.equals(order[j], "D")) {
                    flag = false;
                    break;
                } else if (Objects.equals(order[j], "R")) {
                    Collections.reverse(list);

                } else if (Objects.equals(order[j], "D")) {
                    list.remove(0);
                }
            }

            if (flag && length != 0) {
                sb.append(list).append("\n");
            } else {
                sb.append("error\n");
            }

        }

        System.out.println(sb);
    }
}

조건에 충실해서 만들어본 코드.

reverse 메소드를 사용할 수 있도록 arraylist 사용.

시간초과 (1%)

수정 코드 1

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

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

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

        for (int i = 0; i < N; i++) {
            boolean flag = true;

            String[] order = br.readLine().split("");

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

            ArrayList<String> list = new ArrayList<>(List.of(br.readLine().split(",")));

            list.set(0, list.get(0).replace("[", ""));
            list.set(list.size()-1, list.get(list.size()-1).replace("]", ""));

            if(length == 0 && Objects.equals(order[0], "D")){
                flag = false;
            }else{
                for (int j = 0; j < order.length; j++) {
                    if (list.isEmpty() && Objects.equals(order[j], "D")) {
                        flag = false;
                        break;
                    } else if (Objects.equals(order[j], "R")) {
                        Collections.reverse(list);

                    } else if(Objects.equals(order[j], "D")){
                        list.remove(0);
                    }
                }
            }

            if(flag){
                sb.append(list).append("\n");
            }else{
                sb.append("error\n");
            }

        }

        System.out.println(sb);
    }
}

길이가 0인 배열에 D함수를 수행했을 때 바로 리스트를 건너뛰도록 수정.

시간초과 (16%)

수정 코드 2

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

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

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

        for (int i = 0; i < N; i++) {
            boolean flag = true;

            String[] order = br.readLine().split("");

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

            ArrayList<String> list = new ArrayList<>(List.of(br.readLine().split(",")));

            list.set(0, list.get(0).replace("[", ""));
            list.set(list.size() - 1, list.get(list.size() - 1).replace("]", ""));

            if (length == 0 && Objects.equals(order[0], "D")) {
                flag = false;
            } else {
                for (int j = 0; j < order.length; j++) {
                    if (Objects.equals(order[j], "R")) {
                        Collections.reverse(list);
                    } else if (Objects.equals(order[j], "D")) {
                        if (list.isEmpty()) {
                            flag = false;
                            break;
                        } else {
                            list.remove(0);
                        }
                    }
                }
            }

            if (flag) {
                sb.append(list).append("\n");
            } else {
                sb.append("error\n");
            }

        }

        System.out.println(sb);
    }
}

D 명령을 수행하는 부분을 합침

수정 코드 3

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

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

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



        for (int i = 0; i < N; i++) {
            boolean isReversed = false;
            boolean flag = true;

            String[] order = br.readLine().split("");

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

            ArrayList<String> list = new ArrayList<>(List.of(br.readLine().split(",")));

            list.set(0, list.get(0).replace("[", ""));
            list.set(list.size() - 1, list.get(list.size() - 1).replace("]", ""));

            if (length == 0 && Objects.equals(order[0], "D")) {
                flag = false;
            } else {
                for (int j = 0; j < order.length; j++) {
                    if (Objects.equals(order[j], "R")) {
                        isReversed = !isReversed;
                    } else {
                        if (list.isEmpty()) {
                            flag = false;
                            break;
                        } else if(isReversed) {
                            list.remove(list.size() - 1);
                        }else{
                            list.remove(0);
                        }
                    }
                }
            }

            if (isReversed) {
                Collections.reverse(list);
            }
            if (flag) {
                sb.append(list).append("\n");
            }  else {
                sb.append("error\n");
            }

        }

        br.close();

        System.out.println(sb);
    }
}

reverse하는 부분을 한 번만 할 수 있도록 변수를 만들어 reverse 됐는지 확인.

stringbuilder에 입력 전에 reverse하도록 함

수정 코드 4

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

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

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


        for (int i = 0; i < N; i++) {
            boolean isReversed = false;
            boolean flag = true;

            String[] order = br.readLine().split("");

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

            ArrayList<String> list = new ArrayList<>(List.of(br.readLine().split(",")));

            list.set(0, list.get(0).replace("[", ""));
            list.set(list.size() - 1, list.get(list.size() - 1).replace("]", ""));

            if (length == 0 && Objects.equals(order[0], "D")) {
                flag = false;
            } else {
                for (int j = 0; j < order.length; j++) {
                    if (Objects.equals(order[j], "R")) {
                        isReversed = !isReversed;
                    } else {
                        if (list.isEmpty()) {
                            flag = false;
                            break;
                        } else if (isReversed) {
                            list.remove(list.size() - 1);
                        } else {
                            list.remove(0);
                        }
                    }
                }
            }

            if (isReversed) {
                Collections.reverse(list);
            }
            if (flag) {
                sb.append("[");
                for (int j = 0; j < list.size(); j++) {
                    sb.append(list.get(j));
                    if (list.size() - 1 != j) {
                        sb.append(",");
                    }
                }
                sb.append("]\n");
            } else {
                sb.append("error\n");
            }

        }

        br.close();

        System.out.println(sb);
    }
}

출력이 잘못돼 수정함.

최종 코드

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

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

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


        for (int i = 0; i < N; i++) {
            boolean isReversed = false;
            boolean flag = true;

            String[] order = br.readLine().split("");

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

            ArrayList<String> list = new ArrayList<>(List.of(br.readLine().split(",")));

            list.set(0, list.get(0).replace("[", ""));
            list.set(list.size() - 1, list.get(list.size() - 1).replace("]", ""));

            if (length == 0 && Objects.equals(order[0], "D")) {
                flag = false;
            } else {
                for (int j = 0; j < order.length; j++) {
                    if (Objects.equals(order[j], "R")) {
                        isReversed = !isReversed;
                    } else {
                        if (length == 0 || list.isEmpty()) {
                            flag = false;
                            break;
                        } else if (isReversed) {
                            list.remove(list.size() - 1);
                        } else {
                            list.remove(0);
                        }
                    }
                }
            }

            if (isReversed) {
                Collections.reverse(list);
            }
            if (flag) {
                sb.append("[");
                for (int j = 0; j < list.size(); j++) {
                    sb.append(list.get(j));
                    if (list.size() - 1 != j) {
                        sb.append(",");
                    }
                }
                sb.append("]\n");
            } else {
                sb.append("error\n");
            }

        }

        br.close();

        System.out.println(sb);
    }
}

list가 비었을 때만 D 입력시 error 하면 출력이 틀리게 나와 length가 0일 때 D 수행시 error가 나올 수 있도록 수정.