https://www.acmicpc.net/problem/10828
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1≤N≤10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
코드
배열
public class Stack_20220124 {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N=sc.nextInt();
String input;
int [] arr =new int[N]; //스택 저장소
int top=-1; //정수가 없는경우 -1이므로
for(int i=0;i<N;i++) {
input=sc.next();
if(input.equals("push")) {
top++;
arr[top]=sc.nextInt();
}
//pop일때
else if(input.equals("pop")) {
if(top==-1) {System.out.println(-1);}
else {
System.out.println(arr[top]);
top--;
}
}
//size 출력
else if(input.equals("size")) {
System.out.println(top+1);
}
//empty출력
else if(input.equals("empty")) {
if(top==-1) {System.out.println(1);}
else { System.out.println(0);}}
//top출력
else if (input.equals("top")) {
if(top==-1) {System.out.println(-1);}
else {
System.out.println(arr[top]);
}
}
}
}
}=> 시간초과 로 기능은 되나 채점이 안됩니다. 그래서 시간이 줄일 수 있는 방법은로 다시 올립니다.
public static int[] stack;
public static int size = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int N = in.nextInt();
stack = new int[N];
for(int i = 0; i < N; i++) {
String str = in.next();
switch (str) {
case "push":
push(in.nextInt());
break;
case "pop":
sb.append(pop()).append('\n');
break;
case "size":
sb.append(size()).append('\n');
break;
case "empty":
sb.append(empty()).append('\n');
break;
case "top":
sb.append(top()).append('\n');
break;
}
}
System.out.println(sb);
}
public static void push(int item) {
stack[size] = item;
size++;
}
public static int pop() {
if(size == 0) {
return -1;
}
else {
int res = stack[size - 1];
stack[size - 1] = 0;
size--;
return res;
}
}
public static int size() {
return size;
}
public static int empty() {
if(size == 0) {
return 1;
}
else {
return 0;
}
}
public static int top() {
if(size == 0) {
return -1;
}
else {
return stack[size - 1];
}
}
연결리스트
class ListStack{
int size; //스택에 들어있는 노드 개수
Node top; //가장 위에 있는 노드
class Node {
int data;
Node next;
Node(int x){
if(ListStack.this.size == 0) //스택이 비어있을 경우
next = null;
else //스택이 비어있지 않을 경우
next = top;
data = x;
}
}
void size() {//스택에 들어있는 정수의 개수 출력
System.out.println(size);
}
void top() {//스택의 가장 위에 있는 정수 출력, 없으면 -1 출력
if(size == 0)
System.out.println(-1);
else
System.out.println(top.data);
}
void isEmpty() {//스택에 비어있으면 1, 아니면 0 출력
if(size == 0)
System.out.println(1);
else
System.out.println(0);
}
//정수 x를 스택에 넣는 연산
void push(int x) {
top = new Node(x); //새로운 삽입된 노드가 top
size++;
}
//스택에서 가장 위에 있는 정수 빼고,그 수 출력.//스택에 정수 없는 경우 -1 출력
void pop() {
if(size == 0)
System.out.println(-1);
else {
Node tmp = top;
System.out.println(tmp.data);
top = tmp.next;
tmp.next = null;
size--;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ListStack stack = new ListStack();
int n = sc.nextInt();
sc.nextLine(); //개행문자 제거
for(int i = 0; i< n ; i++) {
String input = sc.nextLine();//명령 입력
if(input.contains("push")) {
int x = Integer.parseInt(input.substring(5));
stack.push(x);
}
else {
switch(input) {
case "pop":
stack.pop();
break;
case "top":
stack.top();
break;
case "empty":
stack.isEmpty();
break;
case "size":
stack.size();
break;
}
}
}
}
}참고
배운 것을 기록합니다.