[BOJ 길라잡이/Java] 11일차 #5430 AC

알고리즘 분류

- 구현

- 자료 구조

- 문자열

- 파싱

- 덱

 

새로운 언어 AC에는 두 가지 함수 R(뒤집기)와 D(버리기)가 있다.

R: 배열에 있는 수를 뒤집는다.

D: 첫 번째 수를 버린다. 배열이 비어있는데 D를 사용한 경우 에러가 발생한다.

 

각 테스트 케이스에 대해서 입력으로 주어진 정수 배열에

함수를 수행한 결과를 출력한다.

에러가 발생한 경우에는 error를 출력한다.

 

생각했던 방법은 다음과 같았다.

- 입력된 배열을 앞뒤 '[', ']'를 빼고 stringbuilder에 저장한다.

- 함수 p를 하나씩 돌면서 R이면 stringbuilder.reverse()를 하고,

D이면 ','를 기준으로 split하고 제일 앞에 있는 숫자를 ,와 함께 삭제한다.

이때 stringbuilder의 length가 0이라면 error를 출력한다.

- error가 아니라면 []를 포함해서 결과 배열을 출력한다.

StringBuilder 사용 (실패 코드)

import java.io.*;
import java.util.*;

public class Main {
    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();

        for (int i = 0; i < T; i++) { // testcase 만큼 반복
            String p = br.readLine(); // 수행할 함수
            int n = Integer.parseInt(br.readLine()); // 배열 수 개수
            StringBuilder arrSb = new StringBuilder();
            boolean isError = false;
            
            String arr = br.readLine();
            for (String c : arr.split("")) {
                arrSb.append(c);
            }

            arrSb.deleteCharAt(0);
            arrSb.deleteCharAt(arrSb.length() - 1);

            for (char func : p.toCharArray()) {
                if (func == 'R') {
                    arrSb.reverse();
                } else if (func == 'D') {
                    String[] arrD = arrSb.toString().split(",");
                    if (arrSb.length() == 0) {
                        sb.append("error\n");
                        isError = true;
                        break;
                    } else {
                        int len = arrD[0].length();
                        arrSb.delete(0, len + 1);
                    }
                }
            }

            if (isError == false) {
                sb.append("[");
                for (int j = 0; j < arrSb.length(); j++) {
                    sb.append(arrSb.charAt(j));
                }
                sb.append("]\n");
            }
        }

        System.out.println(sb);
    }
}

 

그러나 이 방법은 stringbuilder를 사용해 charAt으로 마지막 출력을 하다 보니,

십의 자리 이상인 수를 출력하기가 어려웠고,

O(T * m * n) 즉 테스트케이스 수 * 명령어 길이 * 배열 길이

만큼의 시간이 걸려 시간 초과에 걸렸다.

 

따라서 다른 방법이 필요했고,

Deque를 사용했다.

 

풀이는 다음과 같다.

- String 배열에 앞뒤 []를 빼고 ,를 기준으로 나눈 숫자들을 저장한다.

- Deque에 순서대로 옮긴다.

- 함수 p를 하나씩 돌면서 R이면 booelan isReversed를 반대로 바꾼다.

D이면 1) isReversed가 true라면 뒤에서 poll(), 2) isReversed가 false라면 앞에서 poll()

이때 deque size가 0이라면 에러를 출력한다.

- 에러가 나지 않았다면, deque가 빌 때까지 1) isReversed가 true면 뒤에서 부터 poll(), 2) false면 앞에서부터 poll()

하고 출력한다.

 

Deque 사용 (성공 코드)

import java.io.*;
import java.util.*;

public class Main {
    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();

        for (int i = 0; i < T; i++) { // testcase 만큼 반복
            String p = br.readLine(); // 수행할 함수
            int n = Integer.parseInt(br.readLine()); // 배열 수 개수
            String input = br.readLine();
            String[] arr = input.substring(1, input.length() - 1).split(",");

            Deque<Integer> dq = new LinkedList<>();
            for (int j = 0; j < n; j++) {
                dq.add(Integer.parseInt(arr[j]));
            }
            
            boolean isError = false;
            boolean isReversed = false;

            for (char func : p.toCharArray()) {
                if (func == 'R') {
                    isReversed = !isReversed;
                } else if (func == 'D') {
                    if (dq.isEmpty()) {
                        sb.append("error\n");
                        isError = true;
                        break;
                    }
                    if (isReversed) dq.pollLast();
                    else dq.poll();
                }
            }

            if (!isError) {
                sb.append("[");
                while(!dq.isEmpty()) {
                    sb.append(isReversed ? dq.pollLast() : dq.poll());
                    if (!dq.isEmpty()) sb.append(",");
                }
                sb.append("]\n");
            }
        }

        System.out.println(sb);
    }
}

 

매번 reverse로 뒤집을 필요 없이

현재 배열이 뒤집힌 상태인지 아닌지를 파악해서

뒤에서부터 poll하느냐, 앞에서부터 poll하느냐를 따지는게

이 문제의 킥이었다.

 

이건 O(T * (n+m))의 시간 복잡도를 가지게 된다.

 

Deque는 생각지도 못했고,

reverse를 안쓰고 flag를 쓰는 것도 생각 못했는데

많이 풀다보면 점차 시야가 넓어질 거라고 믿는다.

 

화이팅!