5430 AC JAVA

이번 문제는 내가 풀었던 문제중에서 가장 억울했던 문제이다..

이 문제를 풀면서 주의해야할 점을 얘기해보고자 한다.

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

 

우선 나는 처음에 이 코드를 풀기 위해서, Collections.reverse()를 이용하여 뒤집어서 하였다.

하지만 이 메서드를 사용하면 아시다시피, 자동으로 정렬이 되는 마법의 메서드가 아닌 사실 내부적으로 어떠한 로직을 통하여 배열을 역순 정렬하는 것이다. 따라서 입력값이 이번 문제처럼 큰 경우 시간초과가 무조건 날 것이다.

아래는 reverse의 실제 소스인데, 보다시피 반복문을 통해 정렬을 하게 되어있다.

따라서 시간초과가 날 수 밖에 없는 것이다.

 

아니 그럼 정렬을 하지 않고 어떻게 이걸 구현할 수 있을까?

예를 들어 

 

RDD

1 2 3 4

>> 4321 >> 321 >> 21 이 된다.

명령어를 문자열로 받은 후, 문자 배열로 나눠서 R이 홀수개 나오면 뒤에서부터 삭제,  짝수개 나오면 앞에서부터 삭제하면 그만인 것이다.

추가로, 읽어들일 때, R이 홀수개 나왔다면 이 역시, 읽어들일때도 뒤에서부터 읽어야 한다.

 

package Queue_dev;
import java.io.*;
import java.util.*;

public class Q5430 {
    static Deque<String> deque = new ArrayDeque<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int i = 0; i < T; i++) {
            String command = br.readLine(); // 명령어
            br.readLine();

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

            while(st.hasMoreTokens())
                deque.add(st.nextToken());

            direction(command);
            deque.clear();
        }

        System.out.println(sb);
    }

    public static void direction(String command) {
        boolean descending = false;

        for (char ch : command.toCharArray()) {
            if (ch == 'R') descending = !descending;

            else if(ch == 'D')
                plzBeAnswer(descending);
            }

        if(deque.isEmpty()) {
            sb.append("error\n"); return;
        }

        Iterator<String> it = (descending)
                ? deque.descendingIterator()
                : deque.iterator();

        sb.append("[");
        while(it.hasNext())
            sb.append(it.next()+",");

        sb.replace(sb.length()-1, sb.length(), "]\n");

    }

    private static void plzBeAnswer(boolean descending) {
        try {
            if (descending)
                deque.removeLast();
            else
                deque.removeFirst();
        }
        catch (NoSuchElementException e) {}
    }
}

위는 정답 코드이다.

 

descending이라는 논리형을 사용하여, 커맨드에 R이 나와서 뒤집어야 한다면, True가 되면서 뒤에서부터 삭제하고,

짝수개 나왔다면 False가 되면서 앞에서부터 삭제한다.

 

이렇게 하면, R의 개수에 따라서 삭제해야 할 위치를 알수있다.

 

그리고 아까 말했듯이, R이 홀수개 나왔다면 descendingIterator()을 이용하여 뒤에서부터 읽어들인다.

하지만 R이 짝수개 나왔다면 뒤에서부터 읽을 필요가 없으므로 앞에서부터 읽어들이면 된다.

 

여기까지 했다면, [1,2,3,4, 까지 만들었을텐데 마지막 콤마는 마지막 문자가 ','가 있을 때만 찾아내서 없애도록 한다.

그리고 마지막으로 "]\n"을 추가하여 자리바꿈을 올바르게 해준다.

 

주의해야 할 점은 입력을 [] 빈 문자열로 했다고 해서 무조건 error을 출력하면 안된다.

그 이유는 "R 0 []"은 error로 출력하는게 아닌 "[]"으로 출력해야 되기 때문이다.

 

추가로 이 코드는 마지막에 수정해서 맞춘 코드이고 나는 고작 마지막 ","를 지우는  2문장 때문에 1시간을 넘게 잡혀있었다..

왜냐면, 이전에 작성한 코드 또한 출력이 정상적으로 출력예시와 일치하지만 빈문자열 때문에 눈에 보이진 않지만 뭔가 걸려있어서 16%에서 자꾸 틀렸다고 오답이 나왔기 떄문이다. 우연히 코드를 엎어 보면서 했더니 정답이 됐고, 하나하나 수정해보면서 어디가 틀린지를 찾아봤었다.

 

나처럼 구현할 때, 출력 예시와 출력결과가 동일한데 틀렸다고 나온다면 아래를 점검해보는걸 추천한다.

 

1. 콤마가 제대로 안지워졌을 가능성이 있다.

2. RD와 DR의 출력결과는 달라야 한다. 동일하다면 올바르게 구현하지 않은 것이다.

3. R 0 []을 입력했을 때, error가 나오면 논리적 에러이다. []로 출력이 되어야 한다.

 

쉽지 않은 문제인데, 나도 사실상 프로그램 공부한 지 2달도 안되었기 때문에 설명하는데 많이 부족할수도 있다.

그래도 짧은 기간만에 이 문제를 풀었다는 뿌듯함이 있다.

문제를 많이 풀면서 더욱 노력해야겠다.