[백준 5430] AC (Java)

 

생각보다 정답 비율이 너무 낮은 것으로 보아 메모리 관리가 필요한 문제라고 생각했다.

메모리를 적게 사용할 방안으로 고민한 첫 번째 시도는 error가 발생할 상황을 exception이 일어나기 전에 처리하는 방법이었다.

 

 

명령어 p에 "D"의 갯수가 입력으로 들어오는 배열의 수 보다 많으면 error가 난다고 생각하여

이를 체크하는 메소드를 구현했고, 배열을 뒤집는 기능은 Collections.reverse()를 이용 했다.

 

 

중간에, UnsupportedOperationException이라는 처음 보는 에러를 보게 되었다.

배열에 담긴 데이터를 조작하기 위해 Arrays.asList()를 이용해 리스트를 변환했는데, 이렇게 리스트로 변환된 데이터를 늘이거나 줄이는 동작을 수행하려고 하면 발생하는 에러라고 한다.

List<String> list = Arrays.asList(formattedInput);
list.remove(0);

이랬던 코드를

List<String> list = new ArrayList<>();
list.addAll(Arrays.asList(formattedInput));
list.remove(0);

요로코롬 바꿔주면 해결된다.

(Why? 자바에 대한 깊은 학습이 필요하리라 판단된다. 나중에 깊이 공부해보는 걸로)

 

 

하지만, 이러한 접근으로 구현한 코드는 다음과 같고 시간 초과로 실패했다.

import java.util.*;

public class Main {
    private static final String FORMAT_ERROR = "error";

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();
        String[] results = new String[T];
        scanner.nextLine();

        for (int i = 0; i < T; i++) {
            String p = scanner.nextLine();
            String[] formatted_p = p.split("");

            int n = scanner.nextInt();
            scanner.nextLine();

            String input = scanner.nextLine();

            if (isError(formatted_p, n)) {
                results[i] = FORMAT_ERROR;
                continue;
            }

            String[] formattedInput = input.replace("[", "").replace("]", "").split(",");
            List<String> list = new ArrayList<>();
            list.addAll(Arrays.asList(formattedInput));

            for (String order : formatted_p) {

                switch (order) {
                    case "R":
                        Collections.reverse(list);
                        break;
                    case "D":
                        list.remove(0);
                        break;
                }
            }

            results[i] = formatResult(list);
        }

        for (int i = 0; i < T; i++) {
            System.out.println(results[i]);
        }
    }

    private static String formatResult(List<String> list) {
        StringBuilder format = new StringBuilder();

        format.append("[");
        list.forEach(element -> format.append(element + ","));
        format.append("]");

        return format.toString().replace(",]", "]");
    }


    private static boolean isError(String[] p, int n) {
        int count = 0;

        for (String s : p) {
            if (s.equals("D")) {
                count++;
            }
        }

        return n < count;
    }
}

 

조금만 생각해보니 또다른 방안을 도출할 수 있었다.

문제를 너무 정직하게 바라봤던 것 같다.

 

 

[핵심] "R"이 뒤집는 것이라해서 데이터를 직접 뒤집고 0번째 데이터를 지우고 있던 것이 많은 메모리를 사용함을 알 수 있었다. "R"이 나온 뒤, "R"이 한 번 더 나오기 전까지 "D"는 맨 마지막 데이터를 지우면 이전 방법보다 훨씬 메모리 효율로 구현이 가능 했다.

 

 

최종 코드

import java.util.*;

public class Main {
    private static final String FORMAT_ERROR = "error";

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();
        String[] results = new String[T];
        scanner.nextLine();

        for (int i = 0; i < T; i++) {
            String p = scanner.nextLine();
            String[] formatted_p = p.split("");

            int n = scanner.nextInt();
            scanner.nextLine();

            String input = scanner.nextLine();

            if (isError(formatted_p, n)) {
                results[i] = FORMAT_ERROR;
                continue;
            }

            String[] formattedInput = input.replace("[", "").replace("]", "").split(",");
            List<String> list = new ArrayList<>();
            list.addAll(Arrays.asList(formattedInput));

            boolean isReverse = false;
            for (String order : formatted_p) {

                switch (order) {
                    case "R":
                        isReverse = !isReverse;
                        break;
                    case "D":
                        if (isReverse) {
                            list.remove(list.size() - 1);
                        } else {
                            list.remove(0);
                        }
                        break;
                }
            }

            if (isReverse) {
                Collections.reverse(list);
            }

            results[i] = formatResult(list);
        }

        for (int i = 0; i < T; i++) {
            System.out.println(results[i]);
        }
    }

    private static String formatResult(List<String> list) {
        StringBuilder format = new StringBuilder();

        format.append("[");
        list.forEach(element -> format.append(element + ","));
        format.append("]");

        return format.toString().replace(",]", "]");
    }


    private static boolean isError(String[] p, int n) {
        int count = 0;

        for (String s : p) {
            if (s.equals("D")) {
                count++;
            }
        }

        return n < count;
    }
}