99클럽 코테 스터디 12일차 TIL - 스택
오늘의 문제
백준 - 10828번: 스택
문제내용과 풀이
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
내 풀이
힌트가 스택/큐 였는데, 잘 기억나지 않아 다시 알아봤다.
스택은 보통 상자에 쌓는 예시를 들고, 큐는 줄서기로 표현한다고 한다. 그래서 스택은 "맨 위", 큐는 "앞, 끝"이라는 표현을 쓰는데, 이렇게 표현하는 이유는 스택은 맨 위(TOP)에서만 넣고 빼며 큐는 앞,끝(FRONT, END) 양쪽을 사용하기 때문이다.
스택 (Stack) : LIFO (Last In, First Out)이며, 마지막에 들어온 요소가 먼저 나간다.
- push(element) : 스택의 맨 위에 요소를 추가한다.
- pop() : 스택의 맨 위에 있는 요소를 제거하고 반환한다. (스택이 비어있으면 예외발생)
- peek() : 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.
- isEmpty() : 스택이 비어 있으면 true, 그렇지 않으면 false를 반환한다.
- size() : 스택에 들어있는 요소의 개수를 반환한다.
큐 (Queue) : FIFO (First In, First Out)이며, 먼저 들어온 요소가 먼저 나간다.
- offer(element) 또는 add(element) : 큐의 끝에 요소를 추가한다.
- poll() 또는 remove() : 큐의 앞에 있는 요소를 제거하고 반환한다. (큐가 비어있으면 null 또는 예외 발생 - remove)
- peek() 또는 element() : 큐의 앞에 있는 요소를 제거하지 않고 반환한다. (큐가 비어있으면 null 또는 예외 발생 - element)
- isEmpty() : 큐가 비어 있으면 true, 그렇지 않으면 false를 반환한다.
- size() : 큐에 들어있는 요소의 개수를 반환한다.
문제 내용을 보니 스택 사용법을 익히라는 것 같았고 스택을 사용했다. 문제에서 -1을 반환하라는 부분은 실제 스택, 큐를 쓸 때 각각의 요소를 반환하는 메서드를 사용 시 비어있으면 오류가 나는 것에 맞춘 것 같다.
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 입력수
Stack<Integer> stack = new Stack<>();
scanner.nextLine();
for (int i = 0; i < n; i++) {
String command = scanner.nextLine();
if (command.startsWith("push")) {
int x = Integer.parseInt(command.split(" ")[1]);
stack.push(x);
} else if (command.equals("pop")) {
if (stack.isEmpty()) {
System.out.println(-1);
} else {
System.out.println(stack.pop());
}
} else if (command.equals("size")) {
System.out.println(stack.size());
} else if (command.equals("empty")) {
System.out.println(stack.isEmpty() ? 1 : 0);
} else if (command.equals("top")) {
if (stack.isEmpty()) {
System.out.println(-1);
} else {
System.out.println(stack.peek());
}
}
}
scanner.close();
}
}
조건만 그대로 맞춰서 출력될 수 있게 끔 했다.
근데 이렇게 Scanner를 쓸 때 마다, 다른사람들의 풀이를 보면 bufferedReader, BufferedWriter를 쓴 사람들이 많았다. 찾아보니 bufferedReader는 Scanner보다 입력 처리가 빠르고 BufferedWriter의 write()는 System.out.println() 보다 출력 처리가 빠르다고 한다.
- bufferedReader, Scanner
- Scanner는 입력을 자동으로 분석(파싱)하고, nextInt() 처럼 특정 타입의 데이터를 자동으로 인식하고 변환하는 과정을 포함한다. 이때 정규식 검사를 통한 데이터 타입 확인과 예외 처리가 내부적으로 수행되어 시간이 더 걸린다.
- BufferedReader는 문자열을 그대로 읽어오는 방식으로, 데이터 분석 없이 단순히 버퍼에 저장된 내용을 반환한다. 이후 프로그래머가 직접 변환(Integer.parseInt)하므로 불필요한 파싱 작업이 없다.
- BufferedWriter, System.out.println()
- BufferedWriter.write()는 실제로 데이터를 출력 장치로 보내기 전에 버퍼에 모아두고, 한 번에 출력한다.
- write()를 여러 번 호출해도 출력이 즉시 발생하지 않으므로, I/O 작업이 누적되어 성능 저하가 발생하지 않는다.
- flush()가 호출되거나 버퍼가 꽉 찰 때에만 I/O 작업이 수행된다.
- System.out.println() 는 출력문마다 출력하기 때문에 그 때마다 I/O 작업이 발생한다.
지금은 문제가 어렵지 않아 속도까지 신경안쓰지만, 앞으로는 그런 문제들이 나올 수 있어서 이걸 쓰는 습관을 들여야 할 것 같다. stringBuilder 도 비슷한 느낌같은데, 다음에 문제가 나오면 알아봐야겠다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
String command = br.readLine();
if (command.startsWith("push")) {
int x = Integer.parseInt(command.substring(5));
stack.push(x);
} else if (command.equals("pop")) {
if (stack.isEmpty()) {
bw.write("-1\n");
} else {
bw.write(stack.pop() + "\n");
}
} else if (command.equals("size")) {
bw.write(stack.size() + "\n");
} else if (command.equals("empty")) {
bw.write((stack.isEmpty() ? 1 : 0) + "\n");
} else if (command.equals("top")) {
if (stack.isEmpty()) {
bw.write("-1\n");
} else {
bw.write(stack.peek() + "\n");
}
}
}
bw.flush();
bw.close();
br.close();
}
}
Split -> substring 으로 바꿀 수 있고 write할때는 nextLine과는 다르게 \n으로 개행해주어야 했다.