스택(10828번)

• 티어 : Sliver 4
• 정답여부 : 정답
• 알고리즘 유형 : 구현, 자료구조,스택
• 시간 제한 : 0.5초

💡문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

💡입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

💡출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

💡예제 입력 1

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

💡예제 출력 1

2
2
0
2
1
-1
0
1
-1
0
3

💡예제 입력 2

7
pop
top
push 123
top
pop
top
pop

💡예제 출력 2

-1
-1
123
123
-1
-1

💡문제요약

• 정수를 저장하는 스택을 구현하여 주어진 조건에 따라 출력을 하면 되는 문제
• 주어진 명령
  • push X: 정수 X를 스택에 넣는 연산
  • pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력
  • size: 스택에 들어있는 정수의 개수를 출력
  • empty: 스택이 비어있으면 1, 아니면 0을 출력
  • top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력

💡알고리즘 설계

1. BuffereadReader을 이용하여 입력받음
2. 첫 줄에 주어진 명령의 수를 입력받
3. stack 타입으로 배열을 하나 만듬
4. for문을 돌려 주어진 명령수 만큼 반복을 돌림
5. 공백을 기준으로 입력된 문자열을 분리하여 s에 첫번째 토큰을 저장
6. s에 각 주어진 조건이 같으면 그에 맞는 조건을 출력하도록 구현

💡 시간복잡도

O(N)

💡작성코드

• Java

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Scanner 너무 시간이 걸림.. 그래서 buffer 씀
		int N = Integer.parseInt(br.readLine()); 
		Stack<Integer> stack  = new Stack<Integer>();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()); 
			String s = st.nextToken();
			if(s.equals("push")) {
				int c = Integer.parseInt(st.nextToken());
				stack.push(c);
			}
			else if (s.equals("pop")) {
				if (stack.isEmpty()) {
					System.out.println(-1);
				}
				else {
					System.out.println(stack.pop()); 
				}
			}
			else if(s.equals("size")) {
				System.out.println(stack.size());
			}
			else if (s.equals("top")) {
				if(stack.isEmpty()) {
					System.out.println(-1);
				}
				else {
					System.out.println(stack.peek());
				}
			}
			else if (s.equals("empty")) {
				if(stack.isEmpty()) {
					System.out.println(1);
				}
				else {
					System.out.println(0);
				}
			}
        }
	}
}		

• python

import sys
input=sys.stdin.readline
N = int(input())
stack = []
def push(M) :
        stack.append(M)
def pop():
    if len(stack) != 0:
        print(stack.pop())
    else : 
        print(-1)
def size():
    print(len(stack))
def top():
    if len(stack) != 0:
        print(stack[-1])
    else :
        print(-1)    
def empty():
    if len(stack) == 0:
        print(1)
    else:
        print(0)
for _ in range(N):
    command = input().split()
    if command[0]=='push':
        push(command[1])
    elif command[0]=='pop':
        pop()
    elif command[0]=='size':
        size()
    elif command[0]=='empty':
        empty()
    elif command[0]=='top':
        top()

💡틀린 이유 or 수정할 부분

다른건 문제가 없었지만 top에서 맨 위에 숫자를 어떻게 가져와야할지 몰라서 틀렸다 ㅠㅠ 그래서 검색을 해보니 스택에 있는 peak 존재를 알게되어서 구현을 할 수 있었다!

그리고 뭔가 좀 더 간단한 코드가 있는지 보던 와중 스택에 기본인 코드를 발견해서 복습을 한번 했다!

💡틀린 부분 수정 or 다른풀이

• Java

int[] stack = new int[N];
int size = 0; 
void push(int item) {
	stack[size] = item;	// size칸에 item을 넣고 size를 1증가 
	size++;
}
int pop() {
	// 데이터가 한 개도 없을 경우 -1
	if(size == 0) {
		return -1;
	}
	// 인덱스는 0부터 시작하므로 최상단에 있는 요소는 항상 size-1 index에 위치한다.
	else {
		int res = stack[size - 1];
		stack[size - 1] = 0;	// 0으로 초기화 해준다.
		size--;
		return res;
	}
}
int size() {
	return size;	// 요소 개수를 반환
} 
int empty() {
	// 스택이 비어있으면 1 반환
	if(size == 0) {
		return 1;
	}
	else {
		return 0;
	}
} 
int top() {
	// 데이터가 한 개도 없을 경우 -1
	if(size == 0) {
		return -1;
	}
	// 인덱스는 0부터 시작하므로 최상단에 있는 요소는 항상 size-1 index에 위치한다.
	else {
		return stack[size - 1];
	}
}

💡느낀점 or 기억할 정보

peek 꼭 기억을 해자!