[BOJ] 5430 - AC (Java)

알고리즘

• 구현

• 자료 구조

• 문자열

• 파싱

• 덱

1. 문제

2. Idea

2.1. 시간초과 이슈 발생

import java.util.*;
//Gold_AC
public class BOJ_5430 {
    public static ArrayList<Integer> rev(ArrayList arr){
        Collections.reverse(arr);
        return arr;
    }

    public static ArrayList<Integer> del(ArrayList arr){
        if(arr.size()!=0){arr.remove(0);}
        return arr;
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=Integer.parseInt(sc.nextLine());

        for(int i=0;i<n;i++){
            StringBuilder language=new StringBuilder(sc.nextLine());
            int len=Integer.parseInt(sc.nextLine());
            String list_input= sc.nextLine();
            list_input=list_input.substring(1,list_input.length()-1);

            String[] str_list=list_input.split(",");
            ArrayList<Integer> arr=new ArrayList<>();
            for(int j=0; j<len;j++){arr.add(Integer.parseInt(str_list[j]));}

            for(int j=0; j<language.length();j++){
                if(language.charAt(j)=='R'){rev(arr);}
                else{del(arr);}
            }

            if(arr.size()!=0){System.out.println(arr);}
            else{System.out.println("error");}
        }
    }
}

2.2. 시간초과 이유

ArrayList 사용

ArrayList는 요소를 삭제할 때 뒤의 요소들을 모두 이동 -> 여러번 수행 시 성능 문제가 발생

2.3. 문제 해결

Deque 사용

ArrayList 대신 Deque (LinkedList)를 사용하면, 요소를 앞,뒤에서 빠르게 insert/delete 가능

3. 풀이

3.1. 변수 선언

• t=테스트 케이스의 수

• commands=R(뒤집기), D(삭제) 명령어로 이루어진 문자열

• input=입력된 배열에서 "[", "]"를 제거하고 각 요소를 ","로 split하여 Deque에 저장

int t = Integer.parseInt(sc.nextLine());

String commands = sc.nextLine();
int n = Integer.parseInt(sc.nextLine());
String input = sc.nextLine();
StringTokenizer st = new StringTokenizer(input.substring(1, input.length() - 1), ",");

3.2. Deque 초기화

Deque<Integer> deque = new LinkedList<>();
while (st.hasMoreTokens()) {
	deque.add(Integer.parseInt(st.nextToken()));
}

3.3. R, D 명령어 수행 여부에 대한 변수 선언

• reversed=R 명령어를 수행할 때 배열을 뒤집었는지 여부

• error=D 명령어 수행 중 오류(empty 배열에서 D 명령어를 수행한 경우)가 발생했는지 여부

boolean reversed = false;
boolean error = false;

3.4. R, D 명령어 수행

commands를 순회하면서,

• 'R' 명령어일 경우, reversed 변수의 값을 반대로 변경하여 배열을 뒤집거나 되돌림

• 'D' 명령어일 경우, Deque가 비어있는지 확인

  • isEmpty() -> error=true로 설정 후 break.

  • ! isEmplty() -> reversed 변수의 상태에 따라 Deque의 앞 또는 뒤에서 요소를 제거

for (char command : commands.toCharArray()) {
	if (command == 'R') {reversed = !reversed;} 
	else if (command == 'D') {
		if (deque.isEmpty()) {
			error = true;
			break;
 		}
		if (reversed) {deque.pollLast();} 
		else {deque.pollFirst();}
	}
}

3.5. error 확인

• error 변수를 확인하여 오류가 발생했는지 여부를 파악 후, 오류가 없다면 배열 출력

if (error) {System.out.println("error");} 
else {
	StringBuilder result = new StringBuilder("[");
	if (!reversed) {
		while (!deque.isEmpty()) {
			result.append(deque.pollFirst());
			if (!deque.isEmpty()) {result.append(",");}
        }
	} 
	else {
		while (!deque.isEmpty()) {
			result.append(deque.pollLast());
			if (!deque.isEmpty()) {result.append(",");}
		}
	}
	result.append("]");
	System.out.println(result);
}

4. 전체 코드

import java.util.*;
public class BOJ_5430 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t = Integer.parseInt(sc.nextLine());

        for (int i = 0; i < t; i++) {
            String commands = sc.nextLine();
            int n = Integer.parseInt(sc.nextLine());
            String input = sc.nextLine();

            Deque<Integer> deque = new LinkedList<>();
            StringTokenizer st = new StringTokenizer(input.substring(1, input.length() - 1), ",");
            while (st.hasMoreTokens()) {
                deque.add(Integer.parseInt(st.nextToken()));
            }

            boolean reversed = false;
            boolean error = false;

            for (char command : commands.toCharArray()) {
                if (command == 'R') {reversed = !reversed;} 
                else if (command == 'D') {
                    if (deque.isEmpty()) {
                        error = true;
                        break;
                    }
                    if (reversed) {deque.pollLast();} 
                    else {deque.pollFirst();}
                }
            }

            if (error) {System.out.println("error");} 
            else {
                StringBuilder result = new StringBuilder("[");
                if (!reversed) {
                    while (!deque.isEmpty()) {
                        result.append(deque.pollFirst());
                        if (!deque.isEmpty()) {result.append(",");}
                    }
                } 
                else {
                    while (!deque.isEmpty()) {
                        result.append(deque.pollLast());
                        if (!deque.isEmpty()) {result.append(",");}
                    }
                }
                result.append("]");
                System.out.println(result);
            }
        }
    }
}