[백준] 5430번: AC - JAVA

문제 링크

BOJ 5430번: AC

5430번: AC

풀이 과정

명령어가 R이면 배열 전체를 뒤집고, D라면 첫번째 인자를 삭제하기 때문에 전체 배열을 뒤집는 경우는 $O(N)$의 시간복잡도가 소요되기 때문에, 배열을 직접 뒤집는게 아닌 조건에 따라 앞과 뒤에서 삭제하는 방식을 사용하기로 했다.

때문에, 앞과 뒤에서 pop을 자유롭게 할 수 있는 Deque를 활용하기로 했다.

 

입력의 앞과 뒤에 붙은 괄호를 제거하기 위해 substring(1, str.length())를 활용해 앞뒤로 한 개씩 삭제해 주었고,  split을 사용해 ','을 기준으로 잘라주었다.

주의할 점은 만약 입력이 빈 괄호가 들어 왔을 경우, ""가 반환되어 숫자로 형변환 할 수 없는 에러가 발생할 수 있어 처리가 반드시 필요하다.

reverse라는 boolean 변수를 두고 D가 등장할 때마다 reverse = !reverse를 사용해 값을 바꾸어 스위치로 활용하였다.
reverse == true라면 배열이 뒤집혀진 경우로 뒤에서 요소를 삭제하기 위해 Deque.removeLast 로 뒤의 요소를 삭제하였고, 아니라면 앞에서 삭제하기 위해 Deque.removeFirst를 사용해주었다.

 

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            String p = sc.next();
            int n = sc.nextInt();

            String arrStr = sc.next();
            Deque<Integer> deque = new LinkedList<>();
            for (String s : arrStr.substring(1, arrStr.length() - 1).split(","))
                if (!s.equals(""))
                    deque.add(Integer.valueOf(s));

            System.out.println(ac(deque, p));
        }
    }

    static String ac(Deque<Integer> deque, String commands) {
        boolean reverse = false;

        for (char command : commands.toCharArray()) {
            if (command == 'R')
                reverse = !reverse;
            else {
                if (deque.size() == 0)
                    return "error";

                if (reverse)
                    deque.removeLast();
                else
                    deque.removeFirst();
            }
        }

        StringBuilder sb = new StringBuilder("[");
        while (!deque.isEmpty()) {
            sb.append(reverse ? deque.removeLast() : deque.removeFirst());
            if (deque.size() != 0)
                sb.append(',');
        }
        sb.append(']');

        return sb.toString();
    }
}

 

제출 결과