│문제
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
│풀이 (python)
import sys
N=int(input())
stack=[]
for i in range(N):
order=sys.stdin.readline().split()
if "push" in order:
stack.append(order[-1])
elif "pop" in order:
if len(stack)==0:
print(-1)
else:
print(stack[len(stack)-1])
stack.pop(len(stack)-1)
elif "size" in order:
print(len(stack))
elif "empty" in order:
if len(stack)==0:
print(1)
else:print(0)
elif "top" in order:
if len(stack)==0:
print(-1)
else:print(stack[len(stack)-1])
│설명 (python)
keypoint 1- 속도 sys.stdin.readline()> input()
파이썬 같은 경우 list가 스택의 역할을 하므로 list와 조건문을 통해 간단하게 풀면 되지만,
input()을 사용하여 order를 받는 경우 시간 초과가 발생한다.
sys.stdin.readline()을 활용하면 시간 초과 문제를 쉽게 해결할 수 있다.
│풀이 (c 언어)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int stack[10001];
int count = 0;
int empty() {
if (count == 0) return 1;
else return 0;
}
void push(int num) {
stack[count] = num;
count++;
}
int pop() {
if (empty() == 1) return -1;
else {
count--;
return stack[count];
}
}
int size() {
return count;
}
int top() {
if (empty() == 1) return -1;
else return stack[count-1];
}
int main(void) {
int N;
int num;
scanf("%d", &N);
char order[10];
for (int i = 0; i < N; i++)
{
scanf("%s", &order);
if (!strcmp(order, "push")) {
scanf("%d", &num);
push(num);
}
else if (!strcmp(order, "pop")) printf("%d\n", pop());
else if (!strcmp(order, "size")) printf("%d\n", size());
else if (!strcmp(order, "empty")) printf("%d\n", empty());
else if (!strcmp(order, "top")) printf("%d\n", top());
}
return 0;
}
│설명 (c 언어)
c언어 같은 경우 파이썬보다 속도가 빨라 파이썬과 다르게 시간초과의 문제를 겪지 않는다.
대체로 전역변수 배열을 활용한 방법과 구조체를 활용한 방법 2가지가 있는데, 전역변수 배열을 활용하여 풀이했다.
keypoint 1- 전역변수로 배열을 선언하면 자동으로 초기화 된다.
지역변수로 배열을 선언했을 시 초기화가 안되지만, 전역변수로 배열을 선언한 경우 자동으로 초기화가 된다.
지역변수로 배열을 선언했을시 stack과 같이 메모리 영역에 선언되지만, 전역변수로 선언한 경우 힙영역에 선언되기에 자동으로 초기화된다.
keypoint 2- push 시에 count값을 증가시키므로 top이나 pop에서 count값에 주의하여야 한다.
필자는 첫 문제 풀이시 count값에 유의하지 않고 풀이를 하여 top이나 pop부분에서 오류가 있었다.
pop에서는 count-- 하기때문에 먼저 함으로써 문제가 없지만
top에서는 count는 다음 부분을 가르키므로 -1해주어서 return 하여야한다.