[BOJ 5430] AC - JAVA, Gold5

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

5430번: AC

사용한 알고리즘 : 자료 구조(List) - 구현 문제

 

풀이전략

이 문제에서 가장 신경써야할 부분은 명령어로 'R'이 주어졌을 경우 배열을 뒤집느냐 뒤집지 않느냐이다.

만약 'R' 명령이 들어올 때마다 배열 뒤집기를 실행한다면 최악의 경우 시간 복잡도는 아래와 같다.

 

배열에 들어갈 수 있는 수는 최대 100,000개이고 명령어의 길이 또한 최대 100,000번이 가능하다.

배열 내부의 수가 100,000개 일 때, 'R'로 인해 뒤집기 연산을 수행하면 한 번에 50,000번 연산을 수행해야한다.

(배열의 맨 앞수와 맨 뒤 수가 바뀌면서 뒤집기가 수행되기때문에 배열의 중간지점까지 수행되었을 때 완료된다.

즉, 100,000번의 절반인 50,000번의 연산이 수행되는 것이다.)

따라서 만약 명령어가 100,000개 모두 'R'로 이루어져있을 경우, 100,000 * 50,000번의 연산이 발생한다.

즉 5,000,000,000(50억)번의 연산이 발생하며 JAVA는 초당 1억번의 연산을 수행하므로 50초가

소요되어 시간 초과가 발생한다. (문제에서는 제한 시간을 1초로 줬다.)

 

그러면 시간초과가 발생하지 않도록 하려면 어떻게 해야할까?

여러 방법이 있겠지만, 나는 'R' 명령어가 들어와도 실제로 배열을 한 번도 뒤집지 않으면서 원하는 결과를 도출하여 시간 초과 문제를 해결했다.

 

LinkedList<Integer> list = new LinkedList<Integer>();가 아래 그림과 같이 있다고 생각해보자.

여기서  'D' 연산을 수행해야 한다면, list.remove(0); 연산을 통해 맨 앞 노드를 삭제할 것이다.

ArrayList가 아닌 LinkedList로 되어있기 떄문에 삭제한 노드들 이후의 노드들을 앞으로 당길 필요가 없어 1의 연산이 수행된다.

 

그런데 뒤집기 'R' 연산을 실제로 수행해야한다면 아까 말했듯이 'list.size() / 2' 만큼의 연산이 수행되어야 할 것이다.

하지만 실제로 뒤집기를 수행하지않고, 'R' 연산이 수행될 때마다 배열의 삭제 위치를 변경하면 어떨까?

기존에는 list의 맨 앞 노드를 삭제했다면, 'R' 연산이 수행됐을 때는 list의 맨 뒤 노드를 삭제하는 방법으로 말이다.

 

(LinkedList로 각 수가 노드로서 연결되어야 하지만, 편의상 배열과 같이 그림을 작성했다.)

 

위 그림처럼 실제로는 'R'연산 시 list를 뒤집지 않고, 삭제 위치만 변경하여 노드를 삭제해준다.

그러면 'D', 'R' 명령어 모두 1번의 연산으로 명령을 수행할 수 있게된다.

 

그러면 최악의 경우 list의 길이가 100,000이고 명령어가 100,000번 수행되면서 모두 'R'일지라도

100,000 * 1로 100,000(10만)번의 연산만 수행하면 된다.

JAVA는 초당 1억번의 연산을 수행할 수 있다고 했으므로 0.001초만에 연산 수행이 가능해지는 것이다.

이는 이전 방법보다 약 50,000배 더 빠른 연산을 수행하면서 정답을 도출해낸다.

 

그리고 list의 노드들을 출력할 때도 list를 뒤집어 출력할 필요가 없다.

만약 'R' 연산이 홀수 번 수행되어 list를 거꾸로 출력해야 한다 할지라도

단지 list를 맨 뒷 노드부터 차례로 출력하면 될 뿐이다.

 

※추가적인 시간 절약 Tip

1. 추가 및 삭제 연산을 수행할 때는 LinkedList를 사용하고, 검색 연산을 수행할 때는 ArrayList를 사용하도록 했다.

이유는 LinkedList는 추가 및 삭제 연산에 드는 비용이 O(1)이지만, ArrayList는 O(n)이고

LinkedList는 검색 연산에 드는 비용이 O(n)이지만, ArrayList는 O(1)로 더 효율적이기 때문이다.

 

2. StringBuilder를 사용하여 출력할 때의 비용을 최소화하였다.

 

제출코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;

public class Main{
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for(int t=0;t<T;++t){
            String command = br.readLine();
            int arrCnt = Integer.parseInt(br.readLine());
            String arrStrInput = br.readLine();

            arrStrInput=arrStrInput.substring(1,arrStrInput.length()-1);
            String arrStr[] = arrStrInput.split(",");

            LinkedList<String> list = new LinkedList<>();
            for(int i=0;i<arrCnt;++i){
                list.add(arrStr[i]);
            }

            boolean isError = false;
            boolean isReverse = false;
            for(int i=0;i<command.length();++i){
                if(command.charAt(i)=='R'){
                    isReverse=(!isReverse);
                }
                else if(command.charAt(i)=='D'){
                    if(!list.isEmpty()){
                        if(isReverse) list.remove(list.size()-1);
                        else list.remove(0);
                    }
                    else{
                        isError=true;
                        break;
                    }
                }
            }
            ArrayList<String> arrayList = new ArrayList<>(list);

            if(isError) sb.append("error\n");
            else{
                sb.append("[");
                if(isReverse){
                    for(int i=arrayList.size()-1;i>=0;--i){
                        sb.append(arrayList.get(i));
                        if(i>0) sb.append(",");
                    }
                }
                else{
                    for(int i=0;i<arrayList.size();++i){
                        sb.append(arrayList.get(i));
                        if(i<arrayList.size()-1) sb.append(",");
                    }
                }
                sb.append("]\n");
            }
        }
        System.out.println(sb);
    }
}