[ 백준 28278번 문제 ] 스택 2 - JAVA

이번 글에서는 백준 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

 

백준에서는 여러 프로그래밍 언어 중 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);
    }
}