[백준] 5430 AC - Java

문제 - AC 

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

 

 

문제 설명

 

입력 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

 

출력

 

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

 

 

예제 입력

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

 

 

예제 출력

[2,1]
error
[1,2,3,5,8]
error

---

 

접근 방법

 

- 처음 문제를 봤을때 R, D 명령어에 따라 데이터를 조작해서 하면 되겠다라고 생각하고 이 문제에 맞는 자료구조가 뭐가 있지 생각했었다

- 일단 D에서 첫 번째 수를 버리는 함수 라고 했을때 queue를 생각 했다 

- 하지만 R에서 배열을 뒤집는 함수를 보면 queue를 쓰면 안되겠구나 라고 생각을 했다

- 그럼 어떤걸 사용할까? 생각하다가 양쪽으로 데이터 삽입, 삭제가 다 가능한 Dequeue를 생각했고 결국 Dequeue를 사용하였다

---

코드 작성 (실패 사례)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Objects;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {


    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int testCount = Integer.parseInt(br.readLine());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < testCount; i++) {
                String[] methods = br.readLine().split("");
                int dataCount = Integer.parseInt(br.readLine());
                
                Deque<Integer> queue = Arrays.stream(br.readLine()
                                .replace("[", "")
                                .replace("]", "").split(","))
                        .map(Integer::parseInt).collect(Collectors.toCollection(ArrayDeque::new));

                AC(methods, queue, sb);
            }
            System.out.println(sb);
        }
    }

    public static void AC(String[] methods, Deque<Integer> deque, StringBuilder sb) {

        boolean isReverse = false;

        for (String method : methods) {
            if (Objects.equals("R", method)) {
                isReverse = !isReverse;
                continue;
            }

            if (isReverse) {
                if (deque.pollLast() == null) {
                    sb.append("error\n");
                    return;
                }
            } else {
                if (deque.pollFirst() == null) {
                    sb.append("error\n");
                    return;
                }
            }
        }
        makeResult(sb, deque, isReverse);
    }

    public static void makeResult(StringBuilder sb, Deque<Integer> deque, boolean isReverse) {
        sb.append("[");

        if (!deque.isEmpty()) {
            if (isReverse) {
                sb.append(deque.pollLast());

                while (!deque.isEmpty()) {
                    sb.append(",").append(deque.pollLast());
                }
            } else {
                sb.append(deque.pollFirst());

                while (!deque.isEmpty()) {
                    sb.append(',').append(deque.pollFirst());
                }
            }
        }
        sb.append("]").append("\n");
    }
}

 

- 일단 위 코드는 실패 사례이다

- 위 코드가 틀린점은 만약 데이터가 [] 이런식으로 입력이 받았을때 안에 요소가 없어서 실패한다는 점이다

- 위 코드를 개선하려면 입력 받고 "[", "]" 정규화 처리 해준다음 비어있는지 확인을 한 다음 해줘야 한다 -> 코드가 더러워진다 ㅠ

- 그래서 StrintTokenizer로 입력 받았을때 '[', ']' , "," 이것을 구분자로 사용하여 토큰으로 분리하여 문자열 파싱을 하였다

 

 

코드 작성 (성공 사례)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;
import java.util.StringTokenizer;

public class Main {


    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int testCount = Integer.parseInt(br.readLine());
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < testCount; i++) {
                String[] methods = br.readLine().split("");
                int dataCount = Integer.parseInt(br.readLine());

                StringTokenizer st = new StringTokenizer(br.readLine(), "[],");

                Deque<Integer> queue = new ArrayDeque<>();

                for (int j = 0; j < dataCount; j++) {
                    queue.add(Integer.parseInt(st.nextToken()));
                }
                AC(methods, queue, sb);
            }
            System.out.println(sb);
        }
    }

    public static void AC(String[] methods, Deque<Integer> deque, StringBuilder sb) {

        boolean isReverse = false;

        for (String method : methods) {
            if (Objects.equals("R", method)) {
                isReverse = !isReverse;
                continue;
            }

            if (isReverse) {
                if (deque.pollLast() == null) {
                    sb.append("error\n");
                    return;
                }
            } else {
                if (deque.pollFirst() == null) {
                    sb.append("error\n");
                    return;
                }
            }
        }
        makeResult(sb, deque, isReverse);
    }

    public static void makeResult(StringBuilder sb, Deque<Integer> deque, boolean isReverse) {
        sb.append("[");

        if (!deque.isEmpty()) {
            if (isReverse) {
                sb.append(deque.pollLast());

                while (!deque.isEmpty()) {
                    sb.append(",").append(deque.pollLast());
                }
            } else {
                sb.append(deque.pollFirst());

                while (!deque.isEmpty()) {
                    sb.append(',').append(deque.pollFirst());
                }
            }
        }
        sb.append("]").append("\n");
    }
}

---

풀고 느낀점

 

- 이 문제는 Deque의 자료구조 특성을 알아야 하고 사용 방법도 알아야 풀 수 있는 문제이다

- 그리고 문자열 파싱 어떤 식으로 처리해줘야 하는지에 관해서도 꽤 까다로운 문제이다