A-C

A-C

백준 5430번 문제

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

5430번: AC

 

 

 

 

1. 문제

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 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

 

 

 

 

2. 풀이

■ 풀이 방법

각 함수를 순서대로 시행해서 R은 배열을 뒤집고 D는 배열의 첫 번째를 삭제하는 연산을 하면 될 것 같아 보인다.

그러나 배열을 뒤집는 연산은 시간복잡도가 N이기 때문에 함수 R마다 배열을 뒤집는 연산을 해주면 문제의 주어진 조건에서는 시간 초과가 발생하게 된다.

때문에 매번 순서대로 함수를 시행하는 방법은 사용할 수 없다.

 

문제를 풀기 위해서는 시간복잡도가 큰 R의 연산을 최대한 줄여야 한다.

그런데 사실 주어진 함수를 시행하기 위해 매번 R에 대해 연산을 할 필요는 없고 R함수에 의해서 현재 배열의 상태가 '정순'인지 '역순'인지만 알고 있으면 된다.

 

예를 들어 만약 함수의 조합에서 처음으로 함수 R이 나왔다고 하자 그러면 현재 배열은 역순이 될 것이다.

이 경우, 이후에 나오는 D함수에 대해 지워지는 건 [배열이 정순이였을 때 가장 마지막 위치에 있던 원소]다.

 

그 뒤, 만약 함수의 조합에서 다시 함수 R이 나왔다면 현재 배열은 다시 정순이 될 것이다.

이 경우, 이후에 나오는 D함수에 대해 지워지는 건 [배열의 가장 첫 번째 원소]이다.

 

즉, 함수의 조합에서 R 함수에 대한 연산을 할 필요 없이 현재 배열이 정순인지 역순인지에 따라 D 함수의 연산을 바꿔서 시행해 주기만 하면 된다.

 

그리고 함수의 조합에 따른 D연산을 시행한 후에 최종적으로 현재 배열이 정순인지 역순인지를 판단해서 배열을 바꿔주면 된다.

 

 

 

■ 입력

[입력]

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int total = scanner.nextInt();

    for (int i = 0; i < total; i++) {
        String commend = scanner.next();
        int n = scanner.nextInt();
        String stringArray = scanner.next();

        String substring = stringArray.substring(1, stringArray.length() - 1);   //[1]
        List<String> splitString = Arrays.asList(substring.split(","));
        LinkedList<String> stringList = new LinkedList<>(splitString);   //[2]

        if (substring.isBlank()) {   //[3]
            stringList = new LinkedList<>();  
        }
        
        .
        .
        .
        
     }
}

● [1] : 입력이 [1,...]와 같이 들어오기 때문에 앞 뒤의 '[' 와 ']'를 제거하고 ,를 구분자로 문자열을 나누어서 list에 담는다.

● [2] : 함수 연산에 의해 리스트의 원소가 빈번히 삭제되므로 List를 LinkedList로 변환

● [3] : 입력이 []와 같이 빈 배열이 주어질 경우 위의 방식대로 list를 생성하면 list의 원소로 ""가 저장되므로 이 경우, 빈 list를 할당.

 

 

 

■ doCommend

함수의 조합인 문자열과 list를 받아서 list에 함수의 조합에 대한 연산을 시행하는 메서드

 

[doCommend]

public static void doCommend(String commend, LinkedList<String> list) {
    int length = commend.length();
    boolean isReverse = false;   //[1]

    for (int i = 0; i < length; i++) {   //[2]
        char c = commend.charAt(i);
        if (c == 'R') {   //[3]
            isReverse = !isReverse;
        }
        if (c == 'D') {   //[4]
            if (!isReverse) {
                list.remove(0);
            }
            if (isReverse) {
                list.remove(list.size() - 1);
            }
        }
    }

    if (isReverse) {   //[5]
        Collections.reverse(list);
    }
}

● [1] : 현재 list의 상태가 정순(false)인지 역순(true)인지를 판단하는 플래그

● [2] : 함수의 조합의 길이만큼 반복문 시행

● [3] : 현재 시행되는 함수가 'R'이면 플래그를 바꿔준다.

● [4] : 현재 list의 상태가 정순인지 역순인지에 따라 list에 연산을 시행

● [5] : 연산이 끝난 후 list의 상태가 역순이면 그에 맞춰 list를 뒤집어준다.

 

 

 

■ print

문제의 출력 사양에 맞춰 리스트를 출력해주는 메서드

 

[print]

public static void print(List<String> list) {
    String join = String.join(",", list);
    System.out.println("[" + join + "]");
}

 

 

 

■ 출력

[출력]

public static void main(String[] args) {
       
       .
       .
       .

        for (int i = 0; i < total; i++) {
            
            .
            .
            .

            try {   //[1]
                doCommend(commend, stringList);
            } catch (Exception e) {
                System.out.println("error");
                continue;
            }

            print(stringList);   //[2]
        }
    }

● [1] : 배열이 비어있을 때 D 함수를 시행하면 "error"를 출력해야 하는데 doCommend 시행 시 예외가 발생하는 상황은 외부 요인이 없을 경우 배열이 비어있을 때 D 함수를 시행할 때뿐이므로 try-catch를 사용해서 "error" 출력

● [2] : error 상황이 아닐 경우 연산이 시행된 list 출력

 

 

 

■ 전체 코드

[전체 코드]

public class Main {

    public static void print(List<String> list) {
        String join = String.join(",", list);
        System.out.println("[" + join + "]");
    }

    public static void doCommend(String commend, LinkedList<String> list) {
        int length = commend.length();
        boolean isReverse = false;

        for (int i = 0; i < length; i++) {
            char c = commend.charAt(i);
            if (c == 'R') {
                isReverse = !isReverse;
            }
            if (c == 'D') {
                if (!isReverse) {
                    list.remove(0);
                }
                if (isReverse) {
                    list.remove(list.size() - 1);
                }
            }
        }

        if (isReverse) {
            Collections.reverse(list);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();

        for (int i = 0; i < total; i++) {
            String commend = scanner.next();
            int n = scanner.nextInt();
            String stringArray = scanner.next();

            String substring = stringArray.substring(1, stringArray.length() - 1);
            List<String> splitString = Arrays.asList(substring.split(","));
            LinkedList<String> stringList = new LinkedList<>(splitString);

            if (substring.isBlank()) {
                stringList = new LinkedList<>();
            }

            try {
                doCommend(commend, stringList);
            } catch (Exception e) {
                System.out.println("error");
                continue;
            }

            print(stringList);
        }
    }
}