0x07 - Deque

* P10866 - 덱

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            switch (st.nextToken()) {
                case "push_back" :
                    d.offerLast(Integer.parseInt(st.nextToken()));
                    break;
                case "push_front" :
                    d.offerFirst(Integer.parseInt(st.nextToken()));
                    break;
                case "pop_back" :
                    if(!d.isEmpty()) {sb.append(d.pollLast()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
                case "pop_front" :
                    if(!d.isEmpty()) {sb.append(d.pollFirst()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
                case "size" :
                    sb.append(d.size()).append('\n');
                    break;
                case "empty" :
                    if(d.isEmpty()) {sb.append("1").append('\n');}
                    else {sb.append("0").append('\n');}
                    break;
                case "front" :
                    if(!d.isEmpty()) {sb.append(d.peekFirst()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
                case "back" :
                    if(!d.isEmpty()) {sb.append(d.peekLast()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
            }
        }
        System.out.println(sb);
    }
}

---

* P1021 - 회전하는 큐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        int cnt=0; int[] list = new int[50];
        int tmpcnt=0; boolean success = false;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<k;i++) {list[i]=Integer.parseInt(st.nextToken());}
        Deque<Integer> d = new LinkedList<>();
        for(int i=1;i<=n;i++) {d.offerLast(i);}

        for(int i=0;i<k;i++) {
            success=false; tmpcnt=0;
            int target = list[i];
            while(true) {
                if(target==d.peekFirst()) { //1번연산
                    d.pollFirst();
                    break;
                } else {
                    for(int j=0;j<(d.size()/2+1);j++) { //덱 사이즈 반쪽만큼 왼쪽 츄라이츄라이
                        if(target!=d.peekFirst()) {d.offerLast(d.pollFirst()); tmpcnt++;}
                        else {success=true; cnt+=tmpcnt; break;}
                    }
                    if(!success) { //왼쪽 아니면
                        for(int j=0;j<tmpcnt;j++) {d.offerFirst(d.pollLast());} //원상복구
                        tmpcnt=0;
                        for(int j=0;j<(d.size()/2+1);j++) { //오른쪽으로
                            if(target!=d.peekFirst()) {d.offerFirst(d.pollLast()); tmpcnt++;}
                            else {cnt+=tmpcnt; break;}
                        }
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

---

* P5430 - AC

• 시간초과 / 반례 / 정답
• 많이 틀릴 수록 더 얻어가는 부분이 많은 것 같다 ^-^

* 시간초과 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean success = true; boolean isReversed = false;
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        Deque<Integer> temp = new LinkedList<>();
        for(int i=0;i<n;i++) { //n=100
            success=true; boolean isTemp = false;
            String func = br.readLine();
            int m = Integer.parseInt(br.readLine());
            String inStr = br.readLine();
            String[] inStrArr = inStr.substring(1,inStr.length()-1).split(",");
            d.clear(); temp.clear();
            for(int j=0;j<m;j++) {d.offerLast(Integer.parseInt(inStrArr[j]));}
            //func
            for(int j=0;j<func.length();j++) {
                if(func.charAt(j)=='D') {
                    if(isReversed) {
                        if(isTemp) {
                            int size = temp.size();
                            for(int k=0;k<size;k++) {d.offerLast(temp.pollLast());} //배열개수 < 100000
                            isTemp = false;
                        } else {
                            int size = d.size();
                            for(int k=0;k<size;k++) {temp.offerLast(d.pollLast());}
                            isTemp = true;
                        }
                        if(isTemp) {
                            if(!temp.isEmpty()) {temp.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        } else {
                            if(!d.isEmpty()) {d.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        }
                        isReversed=false;
                    } else { 
                        if(isTemp) { 
                            if(!temp.isEmpty()) {temp.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        } else {
                            if(!d.isEmpty()) {d.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        }
                    }
                } else { // R
                    if(isReversed) {isReversed=false;}
                    else {isReversed=true;}
                }
            }
            if(success) {
                sb.append("[");
                if(isTemp) {
                    int size = temp.size();
                    for (int j = 0; j < size; j++) {sb.append(temp.pollFirst()).append(",");}
                } else {
                    int size = d.size();
                    for (int j = 0; j < size; j++) {sb.append(d.pollFirst()).append(",");}
                }
                sb.deleteCharAt(sb.length()-1);
                sb.append("]").append('\n');
            }
        }
        System.out.println(sb);
    }
}

아무리 생각해도
"테스트케이스만큼 반복 > 함수개수만큼 반복 > 배열뒤집기" 를 수행하면 O(n^3)를 벗어날 수가 없지않나..?
그래도 일단 최대한 줄일 수 있는 부분은 줄여보면서 뒤집어 보려고 했다

• 사용한 방법

1. 뒤집기 : d, temp로 덱 두 개를 사용하여 뒤집기 구현
   • 두 번 옮겨담아서 뒤집는 거 보다는 단축된다고 생각했다
2. isReversed 사용 : 매 번 뒤집는 것이 아니라, R이 홀수번 나왔을 때만 뒤집기 - D를 만났을 때 isReversed 여부를 따져서 뒤집고 잘랐다.
   • 시간초과에 신경이 쏠려서 지금 알았는데 D를 만났을 때만 뒤집고, 실제로 출력할 때는 isReversed 여부를 따지지 않았다. 시간초과가 안 났어도 틀린 풀이였다 ^-^..
   • 정답풀이에서 10% 부족한 생각이었다. 결국 실제로 뒤집기를 실행하는 순간 시간초과가 나므로 여기서 쪼끔만 더 생각해봤으면 됐을텐데..!!!

---

*P5430 - 정답풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean success = true; boolean isReversed = false;
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        for(int i=0;i<n;i++) {
            success=true; isReversed=false;
            String func = br.readLine();
            int m = Integer.parseInt(br.readLine());
            String inStr = br.readLine();
            String[] inStrArr = inStr.substring(1,inStr.length()-1).split(",");
            for(int j=0;j<m;j++) { d.offerLast(Integer.parseInt(inStrArr[j])); }
            //func
            for(int j=0;j<func.length();j++) {
                if(func.charAt(j)=='D') {
                    if(d.isEmpty()) {
                        success = false;
                        sb.append("error").append('\n');
                        break;
                    }
                    if (isReversed) { d.pollLast(); } //뒤집힌 상황이면 : R이 홀수번 나왔다면
                    else { d.pollFirst(); }  //안 뒤집힌 상황이면 : R이 짝수번 나왔다면
                } else { // R
                    if(isReversed) { isReversed=false; }
                    else { isReversed=true; }
                }
            }
            if(success) {
                sb.append("[");
                int size = d.size();
                if(isReversed) {
                    for (int j = 0; j < size; j++) { sb.append(d.pollLast()).append(","); }
                } else {
                    for (int j = 0; j < size; j++) { sb.append(d.pollFirst()).append(","); }
                }
                if(sb.charAt(sb.length()-1)!='['){ sb.deleteCharAt(sb.length()-1); }
                sb.append("]").append('\n');
            }
        }
        System.out.println(sb);
    }
}

• 실제로 뒤집지 않고 R이 홀수번 나왔다면 (isReversed == true)
  - offerFirst → pollLast
  - 넣은 방향과 반대로 출력한다
  • 넣은 방향과 반대에서 자른다

- 알게된점

• 배열을 뒤집는 연산이 필요한 경우 : 실제로 뒤집는 것보다, 앞 뒤로 모두 접근이 가능한 덱을 활용하자

---

* 틀린풀이 - 반례

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean success = true; boolean isReversed = false;
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        for(int i=0;i<n;i++) {
            success=true; isReversed=false;
            String func = br.readLine();
            int m = Integer.parseInt(br.readLine());
            String inStr = br.readLine();
            String[] inStrArr = inStr.substring(1,inStr.length()-1).split(",");
            for(int j=0;j<m;j++) { d.offerLast(Integer.parseInt(inStrArr[j])); }
            //func
            for(int j=0;j<func.length();j++) {
                if(func.charAt(j)=='D') {
                    if(d.isEmpty()) {
                        success = false;
                        sb.append("error").append('\n');
                        break;
                    }
                    if (isReversed) { d.pollLast(); } //뒤집힌 상황이면 : R이 홀수번 나왔다면
                    else { d.pollFirst(); }  //안 뒤집힌 상황이면 : R이 짝수번 나왔다면
                } else { // R
                    if(isReversed) { isReversed=false; }
                    else { isReversed=true; }
                }
            }
            if(success) {
                sb.append("[");
                int size = d.size();
                if(isReversed) {
                    for (int j = 0; j < size; j++) { sb.append(d.pollLast()).append(","); }
                } else {
                    for (int j = 0; j < size; j++) { sb.append(d.pollFirst()).append(","); }
                }
                sb.deleteCharAt(sb.length()-1);
                sb.append("]").append('\n');
            }
        }
        System.out.println(sb);
    }
}

• 반례 : 0 [] 을 넣는 경우
• 자꾸 16%에서 틀려서 오답처리가 됐다.
• sb.deleteCharAt(sb.length()-1); : 이 부분에서 []인 경우에 sb.length()-1인 '['을 삭제해버려서 ]만 출력되었다.
  → 이 반례에 대한 조건을 걸어서 해결했지만, 좀 더 쌈뽕한 풀이가 있지 않을까 싶다..