백준_5430(문자열)

 

다음과 같은 문자열이 입력으로 주어졌다면,

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

 

나는 다음과 같은 방식으로 이 문제를 해결했다.

 

1. 입력받은 수열을 우선 String 배열로 변환한다. ([1,2,3,4] - > String[]{1,2,3,4})

2. 문자열의 첫 위치를 가르키는 start, 마지막을 가르키는 end 인덱스를 사용한다.

3. 명령어 R은 start와 end를 swap한다.

4. 명령어 D는 현재 R이 true인지 false인지에 따라 start를 ++ 혹은 -- 시켜준다.

5. 모든 명령어가 수행된 후 R의 상태에 맞게 반복문을 수행해 결과 문자열을 생성한다.

 

시간복잡도

함수 P는 최대 10만의 길이를 가진다.

P에 따라 수행하는 일은 swap 혹은 start 증감이기 때문에 단순한 상수의 시간대이다.

 

결과 문자열을 만드는 경우 또한 최악의 경우 입력된 수열의 길이 N 만큼 수행된다.

 

=> O(P + N)

 

 

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            String cmd = br.readLine();
            int n = Integer.parseInt(br.readLine());

            String numbers = br.readLine();
            String sub = numbers.substring(1, numbers.length() - 1);

            String[] arr = sub.split(",");

            String output = doFunction(cmd, arr);
            System.out.println(output);
        }
    }

    private static String doFunction(String cmd, String[] arr) {
        StringBuilder res = new StringBuilder("[");
        int start = 0;
        int end = arr.length - 1;
        boolean isReverse = false;
        for (int i = 0; i < cmd.length(); i++) {
            char command = cmd.charAt(i);
            if (command == 'R') {
                int tmp = start;
                start = end;
                end = tmp;
                isReverse = !isReverse;
            } else {
                if (isReverse) {
                    if (end > start || arr[end].equals("")) return "error";
                    start--;
                } else {
                    if (start > end || arr[start].equals("")) return "error";
                    start++;
                }
            }
        }
        if (isReverse) {
            if(end > start) return "[]";

            for (int i = start; i > end; i--) {
                res.append(arr[i] + ",");
            }
        } else {
            if(start > end) return "[]";

            for (int i = start; i < end; i++) {
                res.append(arr[i] + ",");
            }
        }
        res.append(arr[end] + "]");

        return res.toString();
    }
}