반응형

 

이번 글에서는 큐, 스택에 마무리 문제인 24511번 문제를 해결해 보자.
시간 제한과 메모리 제한이 까다로울 것으로 예상된다.

 

 

문제 핵심

  • 첫째 줄 - 자료구조의 수 : N
  • 둘째 줄 - 수열의 종류 : 0 ( Queue ), 1 ( Stack )
  • 셋째 줄 - 자료구조의 초기값 설정
  • 넷째 줄 - 삽입할 수열의 길이 : M
  • 다섯째 줄 - 삽입할 수열의 원소들

풀이 과정

첫 번째 예제의 과정 중 첫 번째 스텝을 다음과 같이 나타낼 수 있다.

그림 처럼 queue와 stack을 구현하여 값을 삽입하고 제거하는 과정으로 구현해보자. 

아마 메모리에서 먼저 초과되지 않을까 싶다.

 

 

1. 자료구조 저장

0, 1과 구별 값에 따라 큐인지 스택인지 구별하여 저장한다.

List<Object> dataStructure = new ArrayList<Object>();
for (int i = 0; i < N; i++) {
    int type = Integer.parseInt(stringTokenizer.nextToken());

    if (type == 0) {
        dataStructure.add(new LinkedList<Integer>());
    } else {
        dataStructure.add(new Stack<Integer>());
    }

}

 

2. 초기 값 저장

세번 째 줄의 초기 값들을 저장한다.

이 때 초기값들은 instanceof를 통해 자료구조를 판별 후 맞는 메소드를 사용한다.

for (int i = 0; i < N; i++) {
    int num = Integer.parseInt(stringTokenizer.nextToken());
    if (dataStructure.get(i) instanceof Queue) {
        ((Queue<Integer>) dataStructure.get(i)).offer(num);
    } else {
        ((Stack<Integer>) dataStructure.get(i)).add(num);
    }
}

 

3. 메인 과정

새로운 값 들이 큐와 스택을 지나면서 반복되는 과정이다.

이 때, 사실 스택이 값을 거쳐가기만 하기 때문에 의미가 없다.

for (int i = 0; i < M; i++) {
    int num = Integer.parseInt(stringTokenizer.nextToken());
    int temp = num;
    for (int j = 0; j < N; j++) {
        if (dataStructure.get(j) instanceof Queue) {
            ((Queue<Integer>) dataStructure.get(j)).add(temp);
            temp = ((Queue<Integer>) dataStructure.get(j)).remove();
        }
    }

    stringBuilder.append(temp).append(" ");

}

 

 

결과는 시간 초과로 메모리 문제가 아닌 2 중 for문에 N과 M의 최악의 경우 (On2)
100,000 * 100,000 = 10,000,000,000 기 때문에 벌어진 일이다.
그렇다면 2 중 for문의 구조를 제거하고,
스택구조에서 값은 지나치기만 하기 때문에 경우에서 제거한다.

 

4. 자료구조의 재구성

그렇다면 큐의 구조일 때 값을 교체하는 과정이고, 그게 여러개라면 하나씩 밀려나는 과정이다.

큐 여러개가 하나의 값만 가지고 있기 때문에 여러개의 큐가 하나의 큐가 되어버린다.

( 즉, 다음과 같은 구조일 때 새로운 값이 들어온다면 하나의 큐처럼 행동한다. )

그렇다면 하나의 큐를 생성하고 큐일 경우에만 값을 추가한다.

Deque<String> queue = new ArrayDeque<>();
StringBuilder stringBuilder = new StringBuilder();
int N = Integer.parseInt(bufferedReader.readLine());


String[] dataStructureString = bufferedReader.readLine().split(" ");
String[] valueString = bufferedReader.readLine().split(" ");
for (int i = 0; i < N; i++) {
    int type = Integer.parseInt(dataStructureString[i]);
    if(type == 0){
        queue.addLast(valueString[i]);
    }
}

 

5. 메인 과정 재구성

다음과 같이 큐의 삽입과 삭제를 반복하면 O(n)의 경우의 수와 메모리 문제가 모두 해결된다.

int M = Integer.parseInt(bufferedReader.readLine());
String[] addValueString = bufferedReader.readLine().split(" ");

for (int i = 0; i < M; i++) {
    queue.addFirst(addValueString[i]);
    stringBuilder.append(queue.removeLast()).append(" ");
}

 

이번 문제는 마치 알고리즘이 큐처럼 행동하게 하여 해결할 수 있었다.
다음과 같이 자료구조의 개념을 이해한다면 여러방법으로 구현할 수 있다.
줄 서거나(큐), 박스에 물건을 넣고 빼거나(스택) 처럼 한 가지로 제한되지 않는다는 점이다.

시간과 메모리를 줄여야 한다는 점에서 이런 구조를 생각할 수 있었던 문제였다.

 

실패 전체 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < N; i++) {
            int type = Integer.parseInt(stringTokenizer.nextToken());

            if (type == 0) {
                dataStructure.add(new LinkedList<Integer>());
            } else {
                dataStructure.add(new Stack<Integer>());
            }

        }

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            if (dataStructure.get(i) instanceof Queue) {
                ((Queue<Integer>) dataStructure.get(i)).offer(num);
            } else {
                ((Stack<Integer>) dataStructure.get(i)).add(num);
            }
        }

        int M = Integer.parseInt(bufferedReader.readLine());

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            int temp = num;
            for (int j = 0; j < N; j++) {
                if (dataStructure.get(j) instanceof Queue) {
                    ((Queue<Integer>) dataStructure.get(j)).add(temp);
                    temp = ((Queue<Integer>) dataStructure.get(j)).remove();
                }
            }

            stringBuilder.append(temp).append(" ");

        }

        System.out.println(stringBuilder);
    }
}

성공 전체 코드


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

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


        String[] dataStructureString = bufferedReader.readLine().split(" ");
        String[] valueString = bufferedReader.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            int type = Integer.parseInt(dataStructureString[i]);
            if(type == 0){
                queue.addLast(valueString[i]);
            }
        }

        int M = Integer.parseInt(bufferedReader.readLine());
        String[] addValueString = bufferedReader.readLine().split(" ");

        for (int i = 0; i < M; i++) {
            queue.addFirst(addValueString[i]);
            stringBuilder.append(queue.removeLast()).append(" ");
        }
        System.out.println(stringBuilder);
    }
}
반응형
반응형
이번 글에서는 백준 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);
    }
}
반응형
반응형
오늘은 자료구조의 기본 구조 중 하나인 큐에 대해서 알아보고자 한다.
가장 기본적인 구조로 선입선출 ( FIFO, First In First Out ) 방식을 가진다.
먼저 온 사람이 나가는 흔히 매장에 줄 서는 과정이라 볼 수 있다.
( Queue 단어 자체가 표 같은 것을 구매하기 위해 줄 서는 것을 의미 )

 

큐 ( Queue )

  • 선입 선출 ( FIFO, First In First Out )
  • 데이터가 들어오는 위치는 가장 뒤 Rear or Back 에서 이루어지고, 데이터가 나가는 위치인 가장 앞 Front, 양쪽에서 삽입 삭제가 이루어진다.
  • BFS ( 너비 우선 탐색 ), 프로세서 핸들링 ( CPU 헤드링 ) 등에 사용.
class Queue{
    private LinkedList<Integer> queue;

    public Queue(){
        queue = new LinkedList<>();
    }
    ....
}

큐의 기본 연산

1. Enqueue(value): 데이터 삽입

  • 큐의 맨 뒤(back)에 데이터를 추가하는 연산
    public void enQueue(int x){
        queue.addLast(x);
    }

 

2. Dequeue(): 데이터 제거

  • 큐의 맨 앞(front)에 있는 데이터를 제거하고 반환하는 연산
    public int depQueue(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.removeFirst();
    }

3. peek() : 최상단 데이터 확인

  • 큐의 맨 앞(front)에 있는 데이터를 반환하지만, 제거하지 않음
    public int peek(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.getFirst();
    }

4. isEmpty(): 큐이 비어 있는지 확인

  • 큐가 비어 있으면 true, 아니면 false 반환
    public boolean isEmpty(){
        return queue.isEmpty() ? true : false;
    }

로직 예시)

1. 빈 큐다

2. Enqueue ( 2 ) 를 통해 가장 앞 부터 채워 넣는다.

3. Enqueue ( 4 ) 를 통해 2 다음에(뒤에서부터) 채워 넣는다.

4. Dequeue 릍 통해 가장 앞에 있는 2를 꺼내고 4를 앞으로 옮긴다.

추가 - JAVA의 큐 관련 클래스

자바에서 큐는 Interface로 구현되어 ArrayDeque, LinkedList, PriorityQueue로 직접 구현할 수 있다.

그 밖에도 Blocking 즉 고정된 크기의 배열을 사용하는 큐도 존재한다.

이는 자바에서 원형 큐의 고정된 크기를 구현하기 위함으로 보인다.

이 글에서는 LinkedList로 정의된 큐와 달리 양쪽에서 삽입과 삭제가 이루어질 수 있는 양방향 큐이며, 메모리 동적인 요소를 가지고 있다.

 

ArrayDeque도 비슷하나 LinkedList와는 다르다. 배열로 사용되며 동적으로 변하긴 하지만, 배열을 다시 늘려야하는 번거로움이 있다. 추후 ArrayList와 LinkedList의 차이에 대해 포스팅할 예정이다.

DeQueue

 양방향에서 삽입/삭제가 이루어 질 수 있는 양방향 큐를 의미한다.

원형 큐

blocking으로 정의된 큐는 원형 큐라고 할 수 있으며 다음과 같은 형태을 가진다.

데이터가 삽입/삭제 됨에 따라 front와 back(rear)를 가리키는 위치가 계속 변하지만, 크기는 고정된 상태로 이루어진다.

다음과 같이 예시를 볼 수 있다.

PriorityQueue

우선순위 큐로 우선순위 비교는 Comparable interface를 활용하여 구현하거나 Comparator를 사용하여 설정할 수 있다.

중복 요소를 허용하고, 정렬된 순서로 요소를 처리하기 때문에 성능에 영향이 줄 수 있는 큐다.

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.add(1);
queue.add(2);

System.out.println(queue.poll());  // 1 (가장 작은 값이 먼저 출력됨)
PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
queue.add(1);
queue.add(3);
queue.add(2);

System.out.println(queue.poll());  // 3 (가장 큰 값이 먼저 출력됨)
이미 많고 다양한 큐가 만들어져 있기 때문에
편한 방법과 
편한 클래스가 자바처럼 다양하게 존재하지만,
기본 자료구조를 이해하지 못한다면 활용하기가 어렵다.
때문에 그걸 사용하기 이전에 기본에 대한 이해를 점검하고 사용하도록 하자.
( ctrl + 클릭 을 통해 자바 클래스 내부를 확인 할 수 있다. )

 

반응형

'알고리즘' 카테고리의 다른 글

플라비우스 요세푸스 순열  (2) 2025.02.28
스택 ( 자료구조 ) - JAVA  (0) 2025.02.04
[ 알고리즘 ] 선택 정렬  (2) 2024.12.12
소수 찾기 ( 에라토스테네스의 체 ) - JAVA  (3) 2024.09.04

+ Recent posts