4회차 결과

후기

 

회전하는 큐와 AC를 풀었다. 요즘 코테 주제를 정해서 자료구조or알고리즘 하나하나 활용해서 익히는 방식으로 연습하고 있다. 이번에는 덱을 중심으로 문제를 풀었고, 두 문제 모두 덱을 사용해야함을 생각해야 하는 문제였다. 사소한 습관도 점검할 수 있었고, 덱을 익숙하게 만든 좋은 학습이었다.

 

 

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

1021번: 회전하는 큐

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

5430번: AC

 

 

 

회전하는 

 

import java.util.*;
import java.io.*;

public class Main{
    public static int N;
    public static int cnt = 0;
    public static Deque<Integer> deq;


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        int M = Integer.parseInt(line[1]);
        deq = new LinkedList<>();
        line = br.readLine().split(" ");

        // deq 초기화
        for(int i=1; i<=N; i++){
            deq.add(i);
        }

        for(String t_ : line){
            int targetN = Integer.parseInt(t_);
            int d1 = indexOf(targetN);
            int d2 = deq.size()-1 - d1; // 주의. N-1이 아니라 size-1을 조심.
            if(d1 <= d2){
                for(int i=0; i<d1; i++)
                    operation2();
            }else{
                for(int i=0; i<=d2; i++)
                    operation3();
            }
            pop();
        }
        System.out.println(cnt);
    }
    public static int indexOf(int number){
        Iterator<Integer> iter = deq.iterator();
        int diff = 0;
        while(iter.hasNext()){
            int num = iter.next();
            if(num == number) break;
            diff++;
        }
        return diff;
    }
    public static void operation2(){
        deq.addLast(deq.pollFirst());
        cnt++;
    }
    public static void operation3(){
        deq.addFirst(deq.pollLast());
        cnt++;
    }
    public static void pop(){
        deq.poll();
    }
}

 

 

AC

 

import java.util.*;
import java.io.*;

public class Main{
    public static int N;
    public static int cnt = 0;
    public static Deque<Integer> deq;


    public static void main(String[] args) throws IOException{
        // 350000(p)개함수 x 350000(n)길이배열
        // 상당하다
        // - 역순 접근이 빨라야 하며
        // - 첫 요소 삭제도 빨라야 함
        // Deque를 사용하자.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> deq;
        int T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; t++){
            String cmd = br.readLine();
            int n = Integer.parseInt(br.readLine());
            String arr = br.readLine();
            // Deque 준비
            deq = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<arr.length(); i++){
                char c = arr.charAt(i);
                if(c==',' || c==']' || c=='['){
                    if(sb.toString().length() != 0){
                        deq.add(Integer.parseInt(sb.toString()));
                        sb = new StringBuilder();
                    }
                    continue;
                }
                sb.append(c-'0');
            }
            // 커맨드를 적용하자.
            boolean reverse = false;
            boolean errorFlag = false;
            for(int i=0; i<cmd.length(); i++){
                char c = cmd.charAt(i);
                switch(c){
                    case 'R':
                        reverse = !reverse;
                        break;
                    case 'D':
                        Integer num = null;
                        if(!reverse)
                            num = deq.pollFirst();
                        else
                            num = deq.pollLast();
                        if(num == null)
                            errorFlag = true;
                }
                if(errorFlag) break;
            }

            // 출력 : 내 문제1: 출력형식에 공백을 검토 안함.. 포함해버림
            if(errorFlag)
                System.out.println("error");
            else{
                if(!reverse){
                    if(deq.size()==0)
                        System.out.println("[]");
                    else
                        System.out.println(deq.toString().replace(" ", ""));
                }else{
                    int[] deqRVS = new int[deq.size()];
                    for(int j=0; j<deqRVS.length; j++){
                        deqRVS[j] = deq.pollLast();
                    }
                    if(deqRVS.length==0) // 내 문제2: deq.size()로 했었음.. 무조건 0인데..
                        System.out.println("[]");
                    else
                        System.out.println(Arrays.toString(deqRVS).replace(" ", ""));
                }
            }
        }
    }
}