🔗 백준 28278 - 스택 2
문제
알고리즘 분류
IDEA
- 앞뒤로 입출력이 발생하므로 문제 이름처럼 스택을 사용해 풀 수 있다.
풀이
- 풀이에 앞서, 나는 이 문제를 6개월 전 푼 적이 있으나 다시 풀이한 것임을 밝힌다.
1-1. 실패한 풀이 - 스택을 이용한 풀이
- Stack을 선언하여 풀었으나, 시간 초과로 실패
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Stack<Integer> stack = new Stack();
for (int i = 0; i<n; i++){
String[] command = br.readLine().split(" ");
switch (command[0]){
case "1":
stack.add(Integer.parseInt(command[1]));
break;
case "2":
if (stack.isEmpty())
System.out.println(-1);
else System.out.println(stack.pop());
break;
case "3":
System.out.println(stack.size());
break;
case "4":
if (stack.isEmpty())
System.out.println(1);
else System.out.println(0);
break;
case "5":
if (stack.isEmpty())
System.out.println(-1);
else System.out.println(stack.peek());
break;
default: break;
}
}
}
}
1-2. 개선한 코드 - ArrayDeque를 이용한 풀이
- 이전에 Collection Framework에 대해 정리하며, Stack보다 ArrayDeque를 권장한다는 내용에 대해 들은 적이 있다. 혹시 Stack구조가 비효율적이라서 시간 초과가 뜬 것이 아닐까 하는 생각에 Stack 대신 ArrayDeque로 선언해봤다.
- 기존의 add, pop, peek 메소드도 addLast, removeLast, getLast로 각각 변경해주었다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i<n; i++){
String[] command = br.readLine().split(" ");
switch (command[0]){
case "1":
stack.addLast(Integer.parseInt(command[1]));
break;
case "2":
if (stack.isEmpty())
System.out.println(-1);
else System.out.println(stack.removeLast());
break;
case "3":
System.out.println(stack.size());
break;
case "4":
if (stack.isEmpty())
System.out.println(1);
else System.out.println(0);
break;
case "5":
if (stack.isEmpty())
System.out.println(-1);
else System.out.println(stack.getLast());
break;
default: break;
}
}
}
}
결과
- ArrayDeque로 바꾸니 맞기는 했지만, 6달 전 풀이에 비하면 시간이 2배 넘게 늘어났기에 이전 코드와 비교해봤다.
게다가 문제 이름이 '스택 2'인 실버4 난이도의 문제에서, 스택을 사용한 풀이가 불가능할 리 없다고 생각했다.
2. 기존(6달 전) 코드 - Stack과 StringBuilder를 이용한 코드
- 오늘날 코드를 작성하며 내가 우려했던 부분과 달리, 기존 코드는 입력도 Scanner로 받았으며 Stack으로 선언되어 있었다.
- 다른 점이라면 출력 시, 매번 출력하는 것이 아니라 StringBuilder를 이용하여 한 번에 처리했다.
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Stack<Integer> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
for(int i = 0; i<n; i++) {
int command = sc.nextInt();
switch(command) {
case (1) :
stack.push(sc.nextInt()); break;
case (2) :
if (stack.isEmpty())
sb.append(-1).append("\n");
else sb.append(stack.pop()).append("\n");
break;
case (3) :
sb.append(stack.size()).append("\n");
break;
case (4) :
if (stack.isEmpty())
sb.append(1).append("\n");
else sb.append(0).append("\n");
break;
case (5) :
if (stack.isEmpty()) sb.append(-1).append("\n");
else sb.append(stack.peek()).append("\n");
break;
}
}
System.out.println(sb);
}
}
최종 코드 - ArrayDeque와 StringBuilder를 사용한 코드
- 새로 코드를 작성하며 ArrayDeque를 활용한 부분은 그대로 두고, 출력 부분만 기존 코드처럼 StringBuilder를 사용하는 방식으로 변경했다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayDeque<Integer> stack = new ArrayDeque<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i<n; i++){
String[] command = br.readLine().split(" ");
switch (command[0]){
case "1":
stack.addLast(Integer.parseInt(command[1]));
break;
case "2":
if (stack.isEmpty())
sb.append(-1+"\n");
else sb.append((stack.removeLast())+"\n");
break;
case "3":
sb.append((stack.size())+"\n");
break;
case "4":
if (stack.isEmpty())
sb.append((1)+"\n");
else sb.append((0)+"\n");
break;
case "5":
if (stack.isEmpty())
sb.append((-1)+"\n");
else sb.append((stack.getLast())+"\n");
break;
default: break;
}
}
System.out.println(sb);
}
}
- 결과는 6달 전 풀이 시간인 2240ms보다도 절반 가까이 줄은 1248ms로 가장 적은 시간 안에 문제를 풀 수 있었다.
- 오랜만에 다시 백준을 풀기 시작해서, 감을 되찾고자 이전에 풀었던 것 중 만만한 것을 골랐는데 StringBuilder의 존재조차 아예 잊어버렸다는 걸 깨달았다. 그래도 이렇게 이전 코드와 비교하며 결론적으로, 현재로서는 가장 나은 풀이를 도출해낼 수 있어 복습하기를 잘 한 듯하다. 이외의 다른 문제들도 복습하고 비교해보면서, 단순 성공/실패 결과를 넘어 더 효율적인 풀이에 대해 고찰해봐야겠다.
