[Gold V] AC - 5430

[Gold V] AC - 5430

문제 링크

성능 요약

메모리: 100472 KB, 시간: 720 ms

분류

덱, 파싱, 구현, 문자열, 자료 구조

제출 일자

2024년 10월 19일 22:03:25

문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x₁,...,x_n]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ x_i ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

---

Deque 자료 구조

위는 Queue 인터페이스의 자료 구조로 Deque 인터페이스는 Queue를 상속받고 있다.

Deque는 데이터 구조 양쪽 끝에서 요소를 추가 및 제거가 가능하며 LinkedList와 ArrayDeque 구현체로 선언할 수 있다.

 

배열 앞 뒤에서 삽입 삭제가 일어나기 때문에 LinkedList로 구현하는 것이 더 효율적것이라고 생각하였지만,

대부분의 상황에서는 ArrayDeque로 구현하는 것이 효율적이라고 하며 이유는 다음과 같다.

 

• 메모리 접근 패턴
  • ArrayDeque는 연속된 메모리 공간을 사용하기 때문에 캐시 효율성이 높다
  • LinkeddList는 노드들이 메모리상에 분산되어 있어 캐시 미스가 더 자주 발생할 수 있다
• 메모리 오버헤드
  • ArrayDeque는 단순 배열을 사용하기에 추가적인 참조 저장이 필요 없다.
  • LinkedList는 각 노드마다 데이터와 함께 이전/다음 노드에 대한 참조를 저장해야 한다.
• 구현 최적화
  • ArrayDeque는 순환 배열 구조를 사용하여 앞뒤 삽입 및 삭제를 효율적으로 처리한다
    • 배열 크기 조정이 필요할 때만 새로운 배열을 할당하고 복사
• 가비지 컬렉션
  • LinkedList는 요소를 추가/제거할 때마다 새로운 노드 객체를 생성/삭제한다
    • 가비지 컬렉션에 부담을 줄 수 있다
• JVM 최적화
  • 현대의 JVM은 배열 기반 구조에 대해 많은 최적화를 수행한다

---

Deque 구조

다음은 Deque의 구조이며 앞서 말했듯 양방향 접근이 가능한 것이 특징이다.

주요 메서드는 다음과 같다.

• addFirst(), offerFirst(): 앞에 요소 추가
• addLast(), offerLast(): 뒤에 요소 추가
• removeFirst(), pollFirst(): 앞에서 요소 제거
• removeLast(), pollLast(): 뒤에서 요소 제거
• getFirst(), peekFirst(): 앞 요소 조회
• getLast(), peekLast(): 뒤 요소 조회

해결 답안

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); 
        StringBuilder sb = new StringBuilder(); 

        for (int i = 0; i < T; i++) { 
            Deque<Integer> dq = new ArrayDeque<>();
            char[] cmds = br.readLine().toCharArray();
            int len = Integer.parseInt(br.readLine());
            String s = br.readLine();
            boolean flag = true;  // true: 정방향, false: 역방향
            boolean isError = false;  // 에러 발생 여부

            if (len > 0) {  // 배열의 길이가 0보다 큰 경우
                String[] arr = s.substring(1, s.length() - 1).split(",");  // 대괄호 제거 후 쉼표로 분리
                for (int j = 0; j < arr.length; j++) {
                    dq.addLast(Integer.parseInt(arr[j]));  // 배열의 각 원소를 Deque에 추가
                }
            }

            for(char cmd : cmds){
                if(cmd == 'R'){  // R 명령어: 배열 뒤집기
                    flag = !flag;  // 방향 전환
                }else{ // D 명령어: 첫 번째 숫자 버리기
                    if(dq.isEmpty()){  // Deque가 비어있으면 에러
                        isError = true;
                    }else{
                        if(flag){  // 정방향이면 앞에서 제거
                            dq.pollFirst();
                        }else{  // 역방향이면 뒤에서 제거
                            dq.pollLast();
                        }
                    }
                }
            }

            if(isError){  // 에러가 발생했으면 "error" 출력
                sb.append("error");
            }else{  // 에러가 없으면 결과 배열 출력
                sb.append("[");
                while(!dq.isEmpty()){
                    if(flag){  // 정방향이면 앞에서부터 출력
                        sb.append(dq.pollFirst());
                    }else{  // 역방향이면 뒤에서부터 출력
                        sb.append(dq.pollLast());
                    }
                    if(!dq.isEmpty()){
                        sb.append(",");  // 원소 사이에 쉼표 추가
                    }
                }
                sb.append("]");
            }

            if(i!=T-1){
                sb.append("\n");  // 마지막 케이스가 아니면 줄바꿈 추가
            }
        }
        System.out.println(sb.toString()); 
        br.close(); 
    }
}

 

출처

https://www.geeksforgeeks.org/deque-interface-java-example/

Deque interface in Java with Example - GeeksforGeeks

https://www.happycoders.eu/algorithms/java-deque-vs-stack/