[백준] 5430번 : AC - 자바(JAVA)

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

5430번: AC

 

문제 해석

두 가지 함수 R(뒤집기)와 D(버리기)가 있습니다.

R은 배열에 있는 수의 순서를 뒤집습니다.

D는 첫번째 수를 버리는 함수입니다.

 

첫 번째 줄에는 테스트 케이스의 개수가 주어집니다. (최대 100개)

각 테스트 케이스의 첫째 줄에는 수행할 함수 p 가 주어집니다. (최대 10만 개)

배열에 들어있는 수의 개수 n이 주어집니다. (최대 10만 개)

다음 줄에는 배열의 정보가 주어집니다.

 

이때 배열이 비어있는데 D를 사용하는 경우에는 에러가 발생합니다.

 

문제 풀이 전 설계

자료구조의 맨 처음 수와 맨 마지막 수를 삭제하는 연산이 발생합니다.

즉, 연결 리스트(LinkedList를 사용하면 효율적인 연산이 가능할 것 같습니다)

 

또한 매번 배열을 실제로 뒤집는 것이 아니라 뒤집혔는지 아닌지 확인하는 문자를 두고 뒤집히지 않았다면 첫 번째를 삭제

뒤집혔다면 마지막을 삭제하는 형태로 연산을 수행합니다.

 

문제를 풀다 보면 시간 초과가 날 수 있는데 여기서 포인트는 number LinkedList에서 값을 가져올때 삭제하면서 가져오면은 항상 O(1)만에 값을 가져오지만 삭제를 하지 않고 가져오면 탐색하는데 시간이 소요되서 시간초과가 발생합니다.

 

코드

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

public class Main_5430_AC {

    static final int UN_REVERSE = -1;

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

        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        outer:
        for (int tc = 0; tc < t; tc++) {
            String function = br.readLine();
            int length = Integer.parseInt(br.readLine());
            String numbers = br.readLine();

            LinkedList<Integer> number = new LinkedList<>();

            String decodeNumbers = numbers.substring(1, numbers.length() - 1);
            if (length == 0 && function.contains("D")) {
                sb.append("error\n");
                continue outer;
            }

            StringTokenizer st = new StringTokenizer(decodeNumbers, ",");
            for (int i = 0; i < length; i++) {
                number.add(Integer.parseInt(st.nextToken()));
            }


            int reverseState = UN_REVERSE;
            int functionLength = function.length();
            for (int i = 0; i < functionLength; i++) {
                if (function.charAt(i) == 'R') {
                    reverseState *= -1;
                    continue;
                }

                if (number.size() == 0) {
                    sb.append("error\n");
                    continue outer;
                }

                if (reverseState == UN_REVERSE) {
                    number.removeFirst();
                } else {
                    number.removeLast();
                }

            }

            StringBuilder result = new StringBuilder();
            result.append("[");
            while (!number.isEmpty()) {
                if (reverseState == UN_REVERSE) {
                    result.append(number.removeFirst());
                } else {
                    result.append(number.removeLast());
                }
                result.append(",");
            }
            if (result.length() != 1) {
                result.deleteCharAt(result.length() - 1);
            }
            result.append("]");

            sb.append(result + "\n");

        }

        System.out.println(sb.toString());
    }
}