BOJ(백준 온라인 저지) 5430번 with 자바[JAVA]

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

5430번: AC

---

리스트를 만들어 요소들을 저장하고 각 명령에 맞게 리스트의 값들을 수정하는 문제입니다.

 

해당 문제에는 2 가지의 명령이 있습니다.

• R: 배열의 순서를 뒤집습니다.
• D: 가장 앞에 요소를 삭제합니다.

만약 배열에 요소가 없을 때, D 명령을 수행하려 하면 error 를 출력하고

아닐 경우는 결과 배열을 출력합니다.

 

특이한 점은 배열의 요소들을 입력해줄 때 [ ] 를 포함하여 입력해준다는 점 입니다.

[ ] 처리를 잘 하는 것이 중요해보입니다.

 

또한 R 연산을 할 때 진짜로 요소들을 일일이 swap 하면 시간초과가 날 것입니다.

 

또한 D 연산을 할 때 요소들이 전부다 한 칸 앞으로 이동하는데, 일반적인 배열을 사용한다면 시간초과가 날 것입니다. 

 

이 3가지 점들을 유의하며 문제를 해결하면 됩니다.

 

 

1. [] 의 처리

 

[]의 처리는 StringTokenizer 를 사용한다면 간단합니다. StringTokenizer 의 구분자를 [ ] , 이렇게 3가지를 주면 해당 구분자를 포함하지 않고 요소들을 분리해줍니다. 이렇게 하면 안에 있는 요소들만 StringTokenizer 의 token 으로 받을 수 있습니다.

 

2. R 연산

 

해당 연산을 정말 swap 을 한다면 한 번 할 때마다 O(n) 의 시간이 걸리고, 이 연산이 m 번 수행된다면 시간복잡도는 O(mn) 입니다. n 의 최대길이는 100,000 이고 최대 수행횟수는 100,000 이니

mn 은 10,000,000,000 으로 100 억입니다. 이는 시간초과를 일으킵니다.

 

이를 해결하기 위해서 isRight 변수를 만들어줍니다.

isRight 이 true 라면 왼쪽에서 오른쪽 방향으로 배열이 진행된다는 의미이고,

isRight 이 false 라면 오른쪽에서 왼쪽 방향으로 배열이 진행된다는 의미입니다.

 

이렇게 한다면 R 연산을 하면 isRight 의 값을 반대값으로 바꿔주면 됩니다.

그리고 D 연산이나 나중에 결과값을 출력해줄때는 isRight 값에 따라 달리 설정해주면 됩니다.

 

3. D 연산

 

일반 배열을 사용한다면 앞에 값이 삭제되는 경우 그 뒤에 있는 값들이 앞으로 한 칸 씩 이동해야 하기 때문에 D 연산 한 번에 최악의 경우 O(n) 의 시간이 걸립니다. R 연산과 마찬가지고 한 번의 연산에 O(n) 의 연산이 소모된다면 시간초과가 일어납니다.

 

이를 해결하기 위해 LinkedList 를 이용합니다. LinkedList 특성상 앞에 요소를 삭제하면 그 뒤에 있는 요소들이 앞으로 한 칸 씩 이동하는 것이 아닌 포인터 값을 변경해주면서 요소들이 앞으로 한 칸 씩 이동하는 효과를 냅니다. 이는 상수시간이 소모되니 시간초과가 발생하지 않습니다.

 

배열의 요소가 하나도 없을 때 D 연산을 수행하려 하면 error 를 출력합니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static boolean errorFlag;
    public static LinkedList<Integer> array;
    public static int arrayLength;
    public static boolean isRight;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();

        int tastCase = Integer.parseInt(br.readLine());
        for(int i=0; i<tastCase; i++)
        {
            /*
            @param isRight: 배열의 읽는 순서를 의미합니다.
            @param errorFlag: 배열의 요소가 없는데 D 연산을 한 경우 errorFlag 값을 true로 바꿔주고 더 이상의 명령을 수행하지 않습니다.
            @param cmds[]: 수행할 명령들의 리스트입니다.
            @param array[]: 요소들을 저장할 배열입니다.
             */
            
            isRight = true;
            errorFlag = false;
            String cmd = br.readLine();
            char[] cmds = new char[cmd.length()];

            for(int j=0; j<cmd.length(); j++)
            {
                cmds[j] = cmd.charAt(j);
            }

            arrayLength = Integer.parseInt(br.readLine());
            array = new LinkedList<>();

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

            for(int j=0; j<arrayLength; j++)
            {
                array.add(Integer.parseInt(st.nextToken()));
            }

            for(int j=0; j<cmds.length; j++)
            {
                switch (cmds[j])
                {
                    case 'D':
                        int result = D();
                        
                        // 배열의 요소가 없는데 D 연산을 수행하는 경우입니다.
                        if(result == -1)
                            errorFlag = true;
                        break;
                    case 'R':
                        R();
                        break;
                    default:
                        break;
                }

                if(errorFlag)
                    break;
            }
            // errorFlag 가 true 이면 error 를 출력해줍니다.
            if(errorFlag)
                sb.append("error").append("\n");
            
            // 배열의 요소가 남아있는 경우의 출력입니다.
            else if(!array.isEmpty())
            {
                // 정방향인 경우 요소를 앞에서부터 뽑아줍니다.
                if(isRight) {
                    sb.append("[");
                    sb.append(array.pollFirst());
                    while(!array.isEmpty())
                    {
                        sb.append(",").append(array.pollFirst());
                    }
                    sb.append("]").append("\n");
                }
                // 역방향인 경우 요소를 뒤에서부터 뽑아줍니다.
                else
                {
                    sb.append("[");
                    sb.append(array.pollLast());
                    while(!array.isEmpty())
                    {
                        sb.append(",").append(array.pollLast());
                    }
                    sb.append("]").append("\n");
                }
            }
            // 요소가 없는 경우 [] 만 출력해줍니다.
            else
            {
                sb.append("[]\n");
            }
        }

        System.out.print(sb.toString());
    }

    private static int D()
    {
        if(array.isEmpty())
            return -1;

        if(isRight)
            array.removeFirst();
        else
            array.removeLast();

        return 0;
    }

    private static void R()
    {
        isRight = !isRight;
    }
}

---

• 느낀 점

자료구조의 종류에 따라 시간초과가 날지 안날지가 정해질 수 있다.

방향을 나타내는 변수로 직접 바꿔주지 않아도 순서가 바뀐 효과를 낼 수 있다.