5430번

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

5430번: AC

이번 문제는 좀 많이 고생한것 같다.

다른 사람들이 올려둔 반례를 참고하고 중간에 시간초과로 다시 방식도 바꿔서 짜다보니 오래 생각하고 풀어본 것 같다.

 

일단 이 문제에서 다루는건 Queue와 Deque라고 할 수 있겠다.

나는 처음에 queue로 짰다가 명령어R을 수행시키는 과정에서 시간초과 요인이 생겨서 백준 질문 게시판에 다른 사람들이 추천한 Deque를 사용했다.

 

우선, 제일 먼저 TestCase의 갯수를 입력 받을 T를 정의하고

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());//테스트 횟수

그 다음에 이 횟수마다 각각 command 명령줄과 배열의 갯수, 배열의 요소를 받아온다.

for(int i=0; i<T; i++){
    char[] command = br.readLine().toCharArray();//배열에 해야할 명령들
    int n = Integer.parseInt(br.readLine());//배열의 요소수
    String arr = br.readLine();
    String[] arrays = arr.substring(1,arr.length()-1).split(",");//타겟 배열
    Deque<Integer> queue = new LinkedList<>();
    for(String s: arrays){
        if(!s.equals("")){
            queue.add(Integer.parseInt(s));
        }
    }

여기서 배열의 요소와 명령어 요소수들을 전부 String으로 받아오기 때문에 각각 명령줄은 charArray와 요소배열은 StringArray로 받아왔다. StringArray로 받아온 이유는 subString와 split으로 가공한 요소들을 담기위해서다.

 

그리고 Deque의 제네릭 타입을 String으로하면 아래의 for문 없이 아래의 코드 한줄로 가능하지만 int타입으로 만들어 보고 싶어서 위처럼 해보았다.

Deque<String> queue = new LinkedList<>(Arrays.asList(arrays));

 

그 다음에, 이제 이 배열에 명령줄을 실행해야하는데 이걸 위해서 따로 Table클래스로 공유 객체를 만들었다.

Table t = new Table(queue,n);

그래서 이 Table 클래스 안에 R과 D 메서드를 구현하고,순서대로 출력하는 order 메서드와 역순으로 명령어가 끝났을때 배열을 출력할 revers메서드도 구현했다.

class Table{
    int n;
    Deque<String> queue;
    boolean b=true;
    boolean direction=true;//true=앞에, false=뒤에
    public Table(Deque<String> queue, int n){
        this.queue=queue;
        this.n=n;
    }
    public void R(){
        this.direction=!direction;
    }
    public void D(){
        try{
            if(direction){
                queue.removeFirst();
            } else {
                queue.removeLast();
            }
        }
        catch (Exception e){
            this.b=false;
        }
    }
    public void order(){
        StringBuilder sb = new StringBuilder();
        if(queue.isEmpty()){
            System.out.println("[]");
        }else {
            sb.append("[").append(queue.removeFirst());
            while (!queue.isEmpty()){
                sb.append(",").append(queue.removeFirst());
            }
            sb.append("]");
            System.out.println(sb);
        }
    }
    public void revers(){
        StringBuilder sb = new StringBuilder();
        if(queue.isEmpty()){
            System.out.println("[]");
        }else {
            sb.append("[").append(queue.removeLast());
            while (!queue.isEmpty()){
                sb.append(",").append(queue.removeLast());
            }
            sb.append("]");
            System.out.println(sb);
        }
    }
}

이에 따라 명령어가 무엇이냐에 따라 공유객체인 table의 R,D메서드를 호출하고 만약 D의 호출수가 요소의 갯수보다 많다면 error를 발생시키도록 했다.

int count = 0;
for (char c : command){
    if(c=='R'){
        t.R();
    } else if (c=='D') {
        count++;
        t.D();
    }
}
if(count>n){
    System.out.println("error");
    continue;
}
if(t.b){
    if(t.direction){
       t.order();
    }
    else{
        t.revers();
    }
}

이 문제에서 찾을 수 있는 반례들은 다음과 같다.

DD

2

[1,2]

------

RDD

2

[1,2]

------

R

2

[1,1]

------

R

0

[]

------

D

0

[]

------

차례대로 결과 값은

[],[],[1,1],[],error이다.

처음에는 배열을 그대로 출력해버려서 배열 중간에 공백이 들어오는 경우가 있었다. 이는 배열을 그대로 출력해서 그런 문제가 생긴 것이었다. 그래서 이 공백을 제거하기위해서 StringBuilder를 사용했고, 공백 문제를 해결했다.

이 공백 문제를 확인하는 반례는 1 D 3 [1,2,3]이다.

 

제네릭 타입을 int로 한 방법

package backjoon;
import java.util.*;
import java.io.*;
public class b5430 {
    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++){
            char[] command = br.readLine().toCharArray();//배열에 해야할 명령들
            int n = Integer.parseInt(br.readLine());//배열의 요소수
            String arr = br.readLine();
            String[] arrays = arr.substring(1,arr.length()-1).split(",");//타겟 배열
            Deque<Integer> queue = new LinkedList<>();
            for(String s:arrays){
                if(!s.equals("")){
                queue.add(Integer.parseInt(s));
                }
            }
            Table t = new Table(queue,n);
            int count = 0;
            for (char c : command){
                if(c=='R'){
                    t.R();
                } else if (c=='D') {
                    count++;
                    t.D();
                }
            }
            if(count>n){
                System.out.println("error");
                continue;
            }
            if(t.b){
                if(t.direction){
                   t.order();
                }
                else{
                    t.revers();
                }
            }
        }
    }
}
class Table{
    int n;
    Deque<Integer> queue;
    boolean b=true;
    boolean direction=true;//true=앞에, false=뒤에
    public Table(Deque<Integer> queue, int n){
        this.queue=queue;
        this.n=n;
    }
    public void R(){
        this.direction=!direction;
    }
    public void D(){
        try{
            if(direction){
                queue.removeFirst();
            } else {
                queue.removeLast();
            }
        }
        catch (Exception e){
            this.b=false;
        }
    }
    public void order(){
        StringBuilder sb = new StringBuilder();
        if(queue.isEmpty()){
            System.out.println("[]");
        }else {
            sb.append("[").append(queue.removeFirst());
            while (!queue.isEmpty()){
                sb.append(",").append(queue.removeFirst());
            }
            sb.append("]");
            System.out.println(sb);
        }
    }
    public void revers(){
        StringBuilder sb = new StringBuilder();
        if(queue.isEmpty()){
            System.out.println("[]");
        }else {
            sb.append("[").append(queue.removeLast());
            while (!queue.isEmpty()){
                sb.append(",").append(queue.removeLast());
            }
            sb.append("]");
            System.out.println(sb);
        }
    }
}

제네릭 타입을 String으로 한 방법

import java.util.*;
import java.io.*;
public class Main {
    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++){
            char[] command = br.readLine().toCharArray();//배열에 해야할 명령들
            int n = Integer.parseInt(br.readLine());//배열의 요소수
            String arr = br.readLine();
            String[] arrays = arr.substring(1,arr.length()-1).split(",");//타겟 배열
            Deque<String> queue = new LinkedList<>(Arrays.asList(arrays));
            Table t = new Table(queue,n);
            int count = 0;
            for (char c : command){
                if(c=='R'){
                    t.R();
                } else if (c=='D') {
                    count++;
                    t.D();
                }
            }
            if(count>n){
                System.out.println("error");
                continue;
            }
            if(t.b){
                if(t.direction){
                    StringBuilder sb = new StringBuilder();
                    if(t.queue.isEmpty()){
                        System.out.println("[]");
                    }else {
                        sb.append("[").append(t.queue.removeFirst());
                        while (!t.queue.isEmpty()){
                            sb.append(",").append(t.queue.removeFirst());
                        }
                        sb.append("]");
                        System.out.println(sb);
                    }
                }
                else{
                    t.revers();
                }
            }
        }
    }
}
class Table{
    int n;
    Deque<String> queue;
    boolean b=true;
    boolean direction=true;//true=앞에, false=뒤에
    public Table(Deque<String> queue, int n){
        this.queue=queue;
        this.n=n;
    }
    public void R(){
        this.direction=!direction;
    }
    public void D(){
        try{
            if(direction){
                queue.removeFirst();
            } else {
                queue.removeLast();
            }
        }
        catch (Exception e){
            this.b=false;
        }
    }
    public void revers(){
        StringBuilder sb = new StringBuilder();
        if(queue.isEmpty()){
            System.out.println("[]");
        }else {
            sb.append("[").append(queue.removeLast());
            while (!queue.isEmpty()){
                sb.append(",").append(queue.removeLast());
            }
            sb.append("]");
            System.out.println(sb);
        }
    }
}