반응형

 

이번 글에서는 큐, 스택에 마무리 문제인 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);
    }
}
반응형
반응형
이번 글에서는 백준 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);
    }
}
반응형
반응형
이번 글에서는 2164번 문제를 통해
큐의 기본 개념을 활용해보자.
사실 이번문제는 거의 브론즈 이하급으로 쉬운 문제이다.

 

문제 핵심

  • 큐를 활용한 카드이다.
  • N장의 카드는 위에서부터 아래로 오름차순으로 정렬되어 있다.
  •  
 

[ 자료구조 ] 큐 ( Queue ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 큐에 대해서 알아보고자 한다.가장 기본적인 구조로 선입선출 ( FIFO, First In First Out ) 방식을 가진다. 먼저 온 사람이 나가는 흔히 매장에 줄 서는 과정이

p-coding.tistory.com

 

풀이 과정

  • 2장의 카드를 한 번의 세트로 움직인다.
    • 한 장을 버리고 그 다음 장을 아래로 움직인다.
    • 값을 두 번 꺼내고 두 번째 값을 삽 하면 된다.

1. 큐 생성

        Queue<Integer> queue = new LinkedList<Integer>();
        
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

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

		for(int i = 1;i <= N; i++){
            queue.add(i);
        }

2. 과정 반복

        while (queue.size() > 1) {
            queue.poll();
            queue.add(queue.poll());
        }

 

기본적인 문제로 큐의 개념만 이해하고 있다면,
바로 쉽게 풀 수 있는 문제이다.

반응형
반응형
오늘은 자료구조의 기본 구조 중 하나인 큐에 대해서 알아보고자 한다.
가장 기본적인 구조로 선입선출 ( 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
반응형
이번 글에서는 4949번 문제를 통해 스택을 활용,
괄호의 균형을 맞춰완벽한 문장을 나타내 보자.


 

 

문제 핵심

  • 문자열은 ( ),  [ ] 이 두 소괄호와 대괄호가 짝을 이루어야 한다.
  • 1 : 1 매칭만 가능하다.
  • 공백 이후의 . 과 같은 괄호가 없는 문장도 균형 잡힌 문자열이다.
  • (, [ 이 나온 후에 ), ] 가 나와야 짝이 이루어 진다. 
    • ] [ 은 짝이 아닌 경우 

풀이 과정

먼저 우리가 찾아야 할 것은 괄호들이다.

이는 StringTokenizer를 활용해 볼 예정이다. ( 물론 chatAt()을 사용하면 더 빠르다. )

다음 자료구조 스택에 대한 글과 split과 StringTokenizer비교에 관한 글을 참고하면 좋을 것 같다.

 

 

스택 ( 자료구조 ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.접시를 쌓아올린다고 생각하면 된다.스택 ( Stack )후

p-coding.tistory.com

 

 

[ JAVA ] 문자열 자르기 Splite VS StringTokenizer

문자열을 특정 구분자로 분리할 수 있는 StringTokenizer와 Splite을 사용하던 중구체적인 차이점이 무엇인지 궁금하여 조사하게 되었다.메모리에서 장점을 가진다고 하지만 정확히 어떤구조로 작용

p-coding.tistory.com

 

 

1. 괄호 문자 저장

먼저 StringTokenizer를 통해 소괄호, 대괄호를 기준으로 문자를 나눈다.

그렇게 되면 구분자를 저장하는 StringTokenizer의 특성을 활용해 문자를 가져올 수 있다.

true로 설정하면 구분자도 Token에 포함된다.

stringTokenizer = new StringTokenizer(sentence,"([)]",true);

 

2. 괄호 문자 찾아 균형확인하기

1. 구분자에 포함된 토큰 중에 괄호를 찾는다.

2. (, [ 라면 스택에 넣는다

3 - 1. ], ) 라면 스택에서 꺼내 비교한다

3 - 2. 이 때, 동일한 모양의 괄호 즉, )일 때 ( 괄호가 나오지 않는다면 균형이 맞지 않는 문자열로 처리

while(stringTokenizer.hasMoreTokens()) {

    String token = stringTokenizer.nextToken();

    if (token.equals("(") || token.equals("[")) {
        push(token);
    }
    else if (token.equals(")")) {
        if (!pop().equals("(")) {
            isPerfect = false;
            break;
        }
    }
    else if (token.equals("]")) {
        if (!pop().equals("[")) {
            isPerfect = false;
            break;
        }
    }
}

 

 

3. 스택에 남아있는 값 확인

마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.

if (!delimStack.isEmpty()) isPerfect = false;

 

스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때,
다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다.
이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이
다양한 방법으로 풀어보는 것을 추천한다.



전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    private static LinkedList<String> delimStack;

    private static void push(String delim){
        delimStack.addLast(delim);
    }

    private static String pop(){
        return delimStack.isEmpty() ? " " : delimStack.removeLast();
    }


    public static void main(String[] args) throws IOException {
        delimStack = new LinkedList<>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        boolean isPerfect;
        StringTokenizer stringTokenizer;

        while (true) {
            isPerfect = true;
            delimStack.clear();
            String sentence = bufferedReader.readLine();

            if(sentence.equals(".")) break;

            stringTokenizer = new StringTokenizer(sentence,"([)]",true);


            while(stringTokenizer.hasMoreTokens()) {

                String token = stringTokenizer.nextToken();

                if (token.equals("(") || token.equals("[")) {
                    push(token);
                }
                else if (token.equals(")")) {
                    if (!pop().equals("(")) {
                        isPerfect = false;
                        break;
                    }
                }
                else if (token.equals("]")) {
                    if (!pop().equals("[")) {
                        isPerfect = false;
                        break;
                    }
                }
            }

            if (!delimStack.isEmpty()) isPerfect = false;


            stringBuilder.append(isPerfect ? "yes\n" : "no\n");
        }

        System.out.println(stringBuilder);
    }
}
반응형
반응형
이번 글에서는 백준 28278번 문제를 통해
스택(자료구조)를 구현하고 활용해 보자.

문제 핵심

  • N : 명령의 수 ( 1 <= N <= 1,000,000 )
  • 명령 1 ~ 5 까지 주어진다.
  • 1. Push
  • 2. Pop
  • 3. Size
  • 4. IsEmpty
  • 5. Peek
  • 명령은 하나씩 주어진다.

풀이 과정

다음 문제는 스택을 구현하고 처리하는 과정이라고 할 수 있다.

 

1. 함수 구현하기

1 ~ 5의 명령어와 같이 스택에 필요한 함수들을 구현하자.

	private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

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

 

문제에 맞게 명령어들을 변형하여 함수를 구현하였다.

2. 구현한 함수 활용하기 ( Main 작성 )

  • 문제를 다음과 같이 풀었지만, 1 ~ 5의 단순한 숫자나 문자열로 처리할 경우 Switch문이 더 적합하며 범위 계산이나 null 값 계산 등이 아니라면 Switch문으로 처리하는 것이 좋아 보인다.
  • List 는 JAVA의 LinkedList<> 클래스를 활용하였다.
    • ArrayList or List를 활용해서 사용할 수 있기도 하지만, 미리 만들어두는 구조보다는 문제제목과 같은 자료구조에 맞춰서 사용하였다.
private static final LinkedList<Integer> list = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

 

 

스택 ( 자료구조 ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.접시를 쌓아올린다고 생각하면 된다.스택 ( Stack )후

p-coding.tistory.com

 

백준에서는 여러 프로그래밍 언어 중 Java가 비교적 느린 편이기 때문에, 많은 사람이 속도 최적화에 집중하거나 단순히 문제를 해결하는 데만 초점을 맞춰 코드를 작성하는 경우가 많다. (물론 브론즈 ~ 실버 수준의 문제에서는 속도 차이가 크게 중요하지 않다.)

하지만 이러한 문제의 핵심은 스택을 직접 구현하고 이해하는 것에 있다.


예를 들어, 명령어가 4일 때 list.isEmpty() ? 1 : 0을 사용하면 간편하게 해결할 수 있다.
그러나 이는 LinkedList 클래스의 isEmpty() 메서드를 활용한 것이지,
우리가 구현해야 할 스택의 isEmpty()가 아니다.

비록 같은 기능을 수행하지만, 개념적으로 다른 의미를 가진다.


즉,
문제를 통과하는 것에만 집중하기보다는, 정확한 개념을 이해하고 접근하는 것이 더 중요하다.


전체 코드

물론 다음 코드도 완벽하지는 않다.

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    private static final LinkedList<Integer> list = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

    private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    private static void push(int num) {
        list.addFirst(num);
    }
}
반응형
반응형
오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.
가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.
접시를 쌓아올린다고 생각하면 된다.


스택 ( Stack )

  • 후입 선출 ( LIFO, Last In First Out )
  • 한쪽 끝에서만 데이터 삽입( push )과 삭제( pop )가 이루어짐
  • 재귀 호출, 백트래킹, 수식 계산 등 다양한 알고리즘에서 활용됨
    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

스택의 기본 연산

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

  • 스택의 맨 위(top)에 데이터를 추가하는 연산
    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

2. pop(): 데이터 제거

  • 스택의 맨 위(top)에 있는 데이터를 제거하고 반환하는 연산
  • 만약 스택이 비어 있다면 언더플로우(Underflow, 데이터 부족 에러) 발생
    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

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

  • 스택의 맨 위(top)에 있는 데이터를 반환하지만, 제거하지 않음
    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

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

  • 스택이 비어 있으면 true, 아니면 false 반환
    public boolean isEmpty() {
        return top == -1;
    }

 

로직 예시)

왼쪽 위부터 오른쪽으로 진행된다

 

1. 빈 스택이다

2. push를 통해 값 ( 1 ) 을 넣었다. 이 때 top은 1을 가리킨다

3. push를 통해 값 ( 2 ) 을 넣었다. 이 때 top은 2를 가리킨다.

4. peek를 통해 값 ( 2 ) 을 받았다.

5. pop을 통해 값 ( 2 ) 를 꺼냈다. 이 때 top은 1을 가리킨다.

6. pop을 통해 값 ( 1 ) 를 꺼냈다. 이 때 top은 아무것도 가리키지 않는다. ( -1 상태 )

 

배열을 활용하여 스택에 대해 설명했지만, 
List 클래스 ( 하위 클래스 포함 ArrayList 등 ) 으로도 구현 가능하다.
 개념을 이해하고 상황에 맞게 사용하면 된다.

전체 구현 코드

package org.example;


public class TestStack {
    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}
반응형
반응형

문제 5, 6번에 적용되는 BaseArray 클래스는 다음과 같다.

class BaseArray {
private:
	int capacity; // 배열의 크기
	int* mem; // 정수 배열을 만들기 위한 메모리의 포인터
protected:
	BaseArray(int capacity = 100)
	{
		this->capacity = capacity; mem = new int[capacity];
	}
	~BaseArray() { delete[]mem; }
	void put(int index, int val) { mem[index] = val; }
	int get(int index) { return mem[index]; }
	int getCapacity() { return capacity; }
};

 

문제

BaseArray 클래스를 상속받아 스택으로 작동하는 Mystack 클래스를 작성하라.

int main()
{
	MyStack mStack(100);
	int n;
	cout << "스택에 삽입할 5개의 정수를 입력하라>> ";
	for (int i = 0; i < 5; i++)
	{
		cin >> n;
		mStack.push(n); //스택에 푸시
	}
	cout << "스택용량:" << mStack.capacity() << ", 스택크기:" << mStack.length() << endl;
	cout << "스택의 모든 원소를 팝하여 출력한다>> ";
	while (mStack.length() != 0) {
		cout << mStack.pop() << ' '; //스택에서 팝
	}
	cout << endl << "스택의 현재 크기 : " << mStack.length() << endl;
}

 

결과

스택에 삽입할 5개의 정수를 입력하라>>1 3 5 7 9
스택 용량 : 100, 스택 크기 : 5
스택의 모든 원소를 팝하여 출력한다>> 9 7 5 3 1
스택의 현재 크기 : 0

 

소스코드

#include<iostream>
using namespace std;
class BaseArray {
private:
	int capacity; // 배열의 크기
	int* mem; // 정수 배열을 만들기 위한 메모리의 포인터
protected:
	BaseArray(int capacity = 100)
	{
		this->capacity = capacity; mem = new int[capacity];
	}
	~BaseArray() { delete[]mem; }
	void put(int index, int val) { mem[index] = val; }
	int get(int index) { return mem[index]; }
	int getCapacity() { return capacity; }
};
class MyStack : public BaseArray {
	int top = -1;
public:
	MyStack(int capacity) : BaseArray(capacity) {};
	void push(int data);
	int capacity();
	int length();
	int pop();
};
void MyStack::push(int data)
{
	if (top >= getCapacity())
	{
		cout << "스택이 가득차있습니다." << endl;
		exit(1);
	}
	put(++top, data);
}
int MyStack::capacity()
{
	return	getCapacity();
}
int MyStack::length()
{
	return top + 1;
}
int MyStack::pop()
{
	if (top <= -1) {
		cout << "스택이 비었습니다.." << endl;
		exit(1);
	}
	return get(top--);
}

int main()
{
	MyStack mStack(100);
	int n;
	cout << "스택에 삽입할 5개의 정수를 입력하라>> ";
	for (int i = 0; i < 5; i++)
	{
		cin >> n;
		mStack.push(n); //스택에 푸시
	}
	cout << "스택용량:" << mStack.capacity() << ", 스택크기:" << mStack.length() << endl;
	cout << "스택의 모든 원소를 팝하여 출력한다>> ";
	while (mStack.length() != 0) {
		cout << mStack.pop() << ' '; //스택에서 팝
	}
	cout << endl << "스택의 현재 크기 : " << mStack.length() << endl;
}
반응형

+ Recent posts