[백준 10866번 덱]

728x90

오늘의 문제는 " 덱 "이다.

 

 

#고민의 흐름

처음엔 무조건 완전탐색!

 

Queue 친구 Deque(Double Ended Queue)의 기능들을 구현하는 문제이다.

명령의 수가 최대 1만 개이고 주어지는 정수는 10만 이하이니 int배열을 선언해 문제를 풀이하면 될 것이라 생각했다.

( LinkedList 를 이용해 풀이할 수 있겠지만,, 솔직히 미뤘다 )

이번엔 int 배열로만 문제를 풀이해 보자 ㅎ

 

방법은 총 2가지이다.

1. 배열 길이를 2만으로 선언해 주어 중간(1만)부터 front, back을 시작해 주는 방법

2. 배열의 길이를 1만으로 선언해주고 front, back을 모듈러 연산을 통해 해결해 주는 방법

( 2번의 경우 배열을 원형 구조라 상상하면 쪼금 더 편한다. )

 

일단 1번 방법을 통해 문제를 풀이해보자.

 

코드는 다음과 같다.

( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

 

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));
        Integer [] arr = new Integer [20010]; // 약간 넉넉히 2만 10으로 선언해주었다.
        StringBuilder sb = new StringBuilder(); // 출력을 돕기 위한 StringBuilder
        int front = 10000; // 맨 앞자리를 가리킬 front
        int back = 10000; // 맨 뒷자리를 가리킬 back
        int N = Integer.parseInt(br.readLine()); // 명령어의 수
        StringTokenizer st;
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken(); // 명령어 받아주기 
            if(str.equals("push_back")){
            // 맨 처음자리 이미 front가 됬을 경우 포함, 다음칸에 수를 넣어주기 위한 조건문이다.
                if(arr[back] != null){
                    back++;
                }
                arr[back] = Integer.parseInt(st.nextToken());
            }else if(str.equals("push_front")){
            // 위와 같은 이유이다.
                if(arr[front] != null){
                    front--;
                }
                arr[front] = Integer.parseInt(st.nextToken());
            }else if(str.equals("pop_front")){
                if(front == back && arr[front] == null){
                // 계속 쓰일 이 배열이 비었다는 가정의 조건.
                    sb.append(-1).append("\n");
                }else{
                // 비지 않았다면 해당자리 출력, 그자리 빈자리만들고 front 자리 갱신
                    sb.append(arr[front]).append("\n");
                    arr[front] = null;
                    if(front != back){
                        front++;
                    }
                }
            }else if(str.equals("pop_back")){
            // 위의 pop_front와 같다.
                if(front == back && arr[front] == null){
                    sb.append(-1).append("\n");
                }else{
                    sb.append(arr[back]).append("\n");
                    arr[back] = null;
                    if(front != back){
                        back--;
                    }
                }
            }else if(str.equals("size")){
                if(front == back && arr[front] == null){
                // 비었다면 0출력
                    sb.append(0).append("\n");
                }else if(front == back && arr[front] != null){
                // 비지 않았으나 front == back일 수 있다. 1번만 push된 경우
                    sb.append(1).append("\n");
                }else{
                // 나머지는 이거면 된다 ㅎ
                    sb.append(back - front + 1).append("\n");
                }
            }else if(str.equals("empty")){
            // 위와 같이 비면 1아니면 0
                if(front == back && arr[front] == null){
                    sb.append(1).append("\n");
                }else{
                    sb.append(0).append("\n");
                }
            }else if(str.equals("front")){
            //비었으면 -1 아니면 front 자리 출력
                if(front == back && arr[front] == null){
                    sb.append(-1).append("\n");
                }else{
                    sb.append(arr[front]).append("\n");
                }
            }else if(str.equals("back")){
            //비었으면 -1 아니면 back 자리 출력
                if(front == back && arr[front] == null){
                    sb.append(-1).append("\n");
                }else{
                    sb.append(arr[back]).append("\n");
                }
            }
        }
        System.out.print(sb);
    }
}

 

 

이번엔 2번 방법을 통해서 문제를 풀이해 보자.

 

이번 코드의 중요한 점.

" back = (back + 10000) % 10000; " 이 예시 코드는( 실제로 아래 있는 코드임 )
front든 back이든 10000 이상이거나, -1 이하인 경우를 해결해 주는 연산이다.
1만을 더해 음수인 경우를 해결하고 최대 명령어 수인 1만으로 모듈러 연산을 해주어
초과되는 경우를 해결해 준다.

 

나머지 부분은 앞선 코드 내용과 유사하므로 한번 봐보자.

 

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));
        Integer [] arr = new Integer [10010]; // 이번엔 최대 명령개수인 1만으로 배열길이 설정.
        StringBuilder sb = new StringBuilder();
        int front = 0;
        int back = 0; // front, back모두 0으로 설정 0 ~ 9999까지 1만자리 사용할 것이다.
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            if(str.equals("push_back")){
            //이전 코드의 내용과 유사하다.
                if(arr[back] != null){
                    back++;
                    back = (back + 10000) % 10000;

                }
                arr[back] = Integer.parseInt(st.nextToken());
            }else if(str.equals("push_front")){
                if(arr[front] != null){
                    front--;
                    front = (front + 10000) % 10000;
                }
                arr[front] = Integer.parseInt(st.nextToken());
            }else if(str.equals("pop_front")){
                if(front == back && arr[front] == null){
                    sb.append(-1).append("\n");
                }else{
                    sb.append(arr[front]).append("\n");
                    arr[front] = null;
                    if(front != back){
                        front++;
                    }
                    front = (front + 10000) % 10000;
                }
            }else if(str.equals("pop_back")){
                if(front == back && arr[front] == null){
                    sb.append(-1).append("\n");
                }else{
                    sb.append(arr[back]).append("\n");
                    arr[back] = null;
                    if(front != back){
                        back--;
                    }
                    back = (back + 10000) % 10000;
                }
            }else if(str.equals("size")){
                if(front == back){
                    if(arr[front] == null){
                        sb.append(0).append("\n");
                    }else{
                        sb.append(1).append("\n");
                    }
                }else if(front > back){
                    sb.append(back + 10000 - front + 1).append("\n");
                }else{
                    sb.append(back - front + 1).append("\n");
                }
            }else if(str.equals("empty")){
                if(front == back && arr[front] == null){
                    sb.append(1).append("\n");
                }else{
                    sb.append(0).append("\n");
                }
            }else if(str.equals("front")){
                if(front == back && arr[front] == null){
                    sb.append(-1).append("\n");
                }else{
                    sb.append(arr[front]).append("\n");
                }
            }else if(str.equals("back")){
                if(front == back && arr[front] == null){
                    sb.append(-1).append("\n");
                }else{
                    sb.append(arr[back]).append("\n");
                }
            }
        }
        System.out.print(sb);
    }
}

 

 

 

과거 부트캠프에서 큐(Queue)와 그 구현에 대해서 배운 기억이 있다.

그때도 배웠던 방법을 응용하여 덱(Deque)을 구현해 보았다.

아직 잊지 않았다는 사실이 다행이다.

추가로 LinkedList를 구현해 보고 이를 통해 문제를 풀어보는 시간도 가져봐야겠다는 생각을 하였다.

 

 

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

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