P-coding

이번 글에서는 백준 2346번 문제를 통해
queue 개념에 관해 좀 더 복잡한 문제를 풀어보자

문제 핵심

• N : 풍선의 개수 ( 자연수 ) 1 ~ 1000
• 각 종이에 이동할 숫자가 적혀 있다. ( 0은 없다 )
• 적힌 종이 별로 양수면 오른쪽, 음수는 왼쪽으로 이동한다.

풀이 과정

다음 Deque를 통해 문제를 풀어 나가며, 인덱스를 기억해 두는 것이 핵심이다.

1. 풍선 번호와 종이 저장

1. 큐에 인덱스 값들을 저장한다.

2. move 정수 배열에 해당 종이를 저장한다.

        Deque<Integer> indexQueue = new ArrayDeque<Integer>();

        int[] move = new int[N];
        for (int i = 0; i < N; i++) {
            move[i] = Integer.parseInt(stringTokenizer.nextToken());
            indexQueue.add(i);
        }

2. 반복

첫 시작은 앞에서부터 시작하기 때문에 미리 처리 한다.

큐에서 꺼낸 값은 인덱스 값이고, 이 인덱스 값을 가지고 move 정수 배열에서 이동할 거리를 확인할 수 있다.

        int removeIndex = indexQueue.removeFirst();
        stringBuilder.append(removeIndex + 1).append(" ");

값을 제외한 후에 for문을 통해 값을 원형 큐 처럼 뒤로 보내기 때문에 -1 한다.

ex) 3번 이동해야 할 때, 값을 제거한다면, 값들이 땡겨지기 때문에 2번 이동한다.

        while(!indexQueue.isEmpty()) {
            int step = move[removeIndex];

            if(step < 0) {
                for(int j = 0; j < -step - 1; j++) {
                    indexQueue.addFirst(indexQueue.removeLast());
                }
                removeIndex = indexQueue.removeLast();

            } else {
                for(int j = 0; j < step - 1; j++) {
                    indexQueue.addLast(indexQueue.removeFirst());
                }
                removeIndex = indexQueue.removeFirst();
            }
            stringBuilder.append(removeIndex + 1).append(" ");
        }

아래의 실패 코드로 이중 리스트 구조로 만들었으나 메모리 초과로 실패하게 되었다.
이 후 불필요한 메모리를 제거하기 위해 분리하여 생성하였고, 성공하였다.

물론 여러 방법 중 하나이니 '틀리다' 라고 말할 수 없겠지만, 
이번 경우는 불필요한 메모리 사용으로 틀렸다고 생각한다.

요즘 컴퓨터 성능은 메모리나 속도면에서 문제 없지만, 막대한 수치가 들어온다면 영향을 끼친다.
때문에 '불필요한' 코드는 줄이도록 하자

실패 코드

다음과 같이 큐 안에 index와 종이의 값들을 모두 넣어서 처리하였으나 과도하게 메모리가 사용되어 메모리 초과되었다.

이후 불필요한 메모리를 제거하기 위해 분리하여 생성하였다.

        Deque<int[]> queue = new LinkedList<>();

전체 코드

package org.example;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(input.readLine());
        StringTokenizer stringTokenizer = new StringTokenizer(input.readLine());
        StringBuilder stringBuilder = new StringBuilder();
        Deque<Integer> indexQueue = new ArrayDeque<Integer>();

        int[] move = new int[N];
        for (int i = 0; i < N; i++) {
            move[i] = Integer.parseInt(stringTokenizer.nextToken());
            indexQueue.add(i);
        }

        int removeIndex = indexQueue.removeFirst();
        stringBuilder.append(removeIndex + 1).append(" ");

        while(!indexQueue.isEmpty()) {
            int step = move[removeIndex];

            if(step < 0) {
                for(int j = 0; j < -step - 1; j++) {
                    indexQueue.addFirst(indexQueue.removeLast());
                }
                removeIndex = indexQueue.removeLast();

            } else {
                for(int j = 0; j < step - 1; j++) {
                    indexQueue.addLast(indexQueue.removeFirst());
                }
                removeIndex = indexQueue.removeFirst();
            }
            stringBuilder.append(removeIndex + 1).append(" ");
        }
        System.out.println(stringBuilder);
    }
}

이번 글에서는 백준 28279번 문제를 통해
deque를 개념을 익혀보자

---

문제 핵심

• N : 명령 수
• 1 ~ 8 까지의 명령어 종류

풀이 과정

다음 Deque를 통해 저번 백준 스택 문제와 같은 형태로 푸는 쉬운 문제이다.

1. 명령어 정의

1 ~ 8에 해당하는 명령어를 정의한다.

Java에는 deque가 존재하지만, 문제에 맞게 처리해야 하기 때문에 다시 정의해준다.

    private static Deque<Integer> queue;

    private static int isEmpty(){
        return queue.isEmpty() ? 1 : 0;
    }

    private static void addFirst(int num) {
        queue.addFirst(num);
    }

    private static void addLast(int num) {
        queue.addLast(num);
    }

    private static int size(){
        return queue.size();
    }

    private static int removeFirst() {
        return queue.isEmpty() ? -1 : queue.removeFirst();
    }

    private static int removeLast() {
        return queue.isEmpty() ? -1 : queue.removeLast();
    }

    private static int getFirst() {
        return queue.isEmpty() ? -1 : queue.getFirst();
    }

    private static int getLast() {
        return queue.isEmpty() ? -1 : queue.getLast();
    }

2. 명령어 분류 처리

 명령어 처리 1 ~ 8 까지의 명령어에 해당하는 함수를 실행한다.

            int command = Integer.parseInt(stringTokenizer.nextToken());

            switch (command) {
                case 1:
                    addFirst(Integer.parseInt(stringTokenizer.nextToken()));
                    break;
                case 2:
                    addLast(Integer.parseInt(stringTokenizer.nextToken()));
                    break;
                case 3:
                    stringBuilder.append(removeFirst() + "\n" );
                    break;
                case 4:
                    stringBuilder.append(removeLast() + "\n" );
                    break;
                case 5:
                    stringBuilder.append(size() + "\n" );
                    break;
                case 6:
                    stringBuilder.append(isEmpty() + "\n" );
                    break;
                case 7:
                    stringBuilder.append(getFirst() + "\n" );
                    break;
                case 8:
                    stringBuilder.append(getLast() + "\n" );
                    break;
            }

아직까지는 실버 문제로 개념만 이해한다면,
문제 조건에 맞게 풀기만 한다면,
아주 쉽게 풀 수 있다.

이후에 해결할 골드이상의 문제에 대비해 이와 같은 문제를 많이 풀어보길 바란다.

전체코드

package org.example;

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

public class Main {
    private static Deque<Integer> queue;

    private static int isEmpty(){
        return queue.isEmpty() ? 1 : 0;
    }

    private static void addFirst(int num) {
        queue.addFirst(num);
    }

    private static void addLast(int num) {
        queue.addLast(num);
    }

    private static int size(){
        return queue.size();
    }

    private static int removeFirst() {
        return queue.isEmpty() ? -1 : queue.removeFirst();
    }

    private static int removeLast() {
        return queue.isEmpty() ? -1 : queue.removeLast();
    }

    private static int getFirst() {
        return queue.isEmpty() ? -1 : queue.getFirst();
    }

    private static int getLast() {
        return queue.isEmpty() ? -1 : queue.getLast();
    }


    public static void main(String[] args) throws IOException {
        queue = new ArrayDeque<>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());
        StringBuilder stringBuilder = new StringBuilder();
        StringTokenizer stringTokenizer;

        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int command = Integer.parseInt(stringTokenizer.nextToken());

            switch (command) {
                case 1:
                    addFirst(Integer.parseInt(stringTokenizer.nextToken()));
                    break;
                case 2:
                    addLast(Integer.parseInt(stringTokenizer.nextToken()));
                    break;
                case 3:
                    stringBuilder.append(removeFirst() + "\n" );
                    break;
                case 4:
                    stringBuilder.append(removeLast() + "\n" );
                    break;
                case 5:
                    stringBuilder.append(size() + "\n" );
                    break;
                case 6:
                    stringBuilder.append(isEmpty() + "\n" );
                    break;
                case 7:
                    stringBuilder.append(getFirst() + "\n" );
                    break;
                case 8:
                    stringBuilder.append(getLast() + "\n" );
                    break;
            }
        }
        System.out.println(stringBuilder);
    }
}