[C#] 백준 10828 스택
https://www.acmicpc.net/problem/10828
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
예제 입력 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
수치 만큼 입력값을 주고, 입력값에 따라 출력해야 할 경우는 값을 출력해주는 식의 코드를 짜달라는 내용이다.
이 문제에서 알아야 할 것은 스택에 대한 것, 그리고 스택의 Pop, Push, Count, Peek 이다.
스택
스택이란 데이터를 저장하고 관리하는 자료구조 중 하나이다. 스택은 후입선출인 LIFO(Last In First Out) 원칙에 따라 동작한다. 그래서 게임에서 스택이 쌓이듯, 테트리스 쌓듯이 가장 최근에 들어온 것이 가장 위에 있다는 특징을 가지고 있다.
스택의 멤버 함수
이 문제를 풀려면 스택의 멤버 함수에 대해 아는 것이 중요하다.
- Push : 스택 안에 데이터 값을 삽입
- Pop : 스택에서 데이터 값을 꺼냄
- Peek : 가장 상단의 데이터를 추출
- Count : 스택의 크기를 인트형으로 반환
- Clear: 스택의 모든 항목을 제거
문제풀이
먼저 count로 몇 번 명령할 지 입력을 받고, 스택을 생성한 후 입력된 count만큼 반복하여 어떤 단어가 입력되었느냐에 따라 어떤 행동을 취할지에 대해 생각하고 코드를 짠다.
1. push
int count = int.Parse(Console.ReadLine());
Stack<int> stacks = new Stack<int>();
for(int i = 0; i < count; i++)
{
string input = Console.ReadLine();
// push
if(input.Contains("push"))
{
int next = input.IndexOf(" ");
string nextNum = input.Substring(next + 1);
if(int.TryParse(nextNum, out next))
stacks.Push(next);
}
}
push의 경우 띄어쓰기 후에 수를 입력하기 때문에 IndexOf로 띄어쓰기의 위치를 파악한 후, 그 다음 오는 값을 int로 파싱해주고 이를 Push해주도록 한다.
2. top
int count = int.Parse(Console.ReadLine());
Stack<int> stacks = new Stack<int>();
for(int i = 0; i < count; i++)
{
string input = Console.ReadLine();
// top
if(input.Contains("top"))
{
if(stacks.Count == 0)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(stacks.Peek()) ;
}
}
}
top 은 가장 위에있는 수를 입력하고, 만약 비어있다면 -1 을 출력하는 내용이다. Peek 메서드로 출력해주도록 하자
3. pop
int count = int.Parse(Console.ReadLine());
Stack<int> stacks = new Stack<int>();
for(int i = 0; i < count; i++)
{
string input = Console.ReadLine();
if (input.Contains("pop"))
{
if(stacks.Count == 0)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(stacks.Pop());
}
}
}
pop은 꺼낼게 없다면 -1을, 아니면 pop할 값을 출력하고 pop해주도록 하자. 다만 주의할 점은 else 부분의 Stack.Pop()을 출력해주면서 동시에 pop이 되기 때문에 한번 더 쓰지 않도록 하자.
4. empty
int count = int.Parse(Console.ReadLine());
Stack<int> stacks = new Stack<int>();
for(int i = 0; i < count; i++)
{
string input = Console.ReadLine();
if (input.Contains("empty"))
{
if(stacks.Count == 0)
Console.WriteLine(1);
else
Console.WriteLine(0);
}
}
empty는 count로 값이 없으면 1, 있으면 0을 출력해주자.
5. size
int count = int.Parse(Console.ReadLine());
Stack<int> stacks = new Stack<int>();
for(int i = 0; i < count; i++)
{
string input = Console.ReadLine();
if (input.Contains("size"))
{
Console.WriteLine(stacks.Count);
}
}
마지막으로 size는 Count함수로 size의 값을 출력해주도록 하자.
시간 초과
시간 초과가 일어났다. Console.WriteLine()의 경우 계속될 경우에는 시간초과가 일어나기 때문에 이렇게 시간초과가 날 경우 StringBuilder 를 이용하여 해결하도록 하자.
정답
using System.Text;
namespace CodeKata8
{
internal class Program
{
static void Main(string[] args)
{
int count = int.Parse(Console.ReadLine());
Stack<int> stacks = new Stack<int>();
StringBuilder cw = new StringBuilder();
for(int i = 0; i < count; i++)
{
string input = Console.ReadLine();
// push
if(input.Contains("push"))
{
int next = input.IndexOf(" ");
string nextNum = input.Substring(next + 1);
if(int.TryParse(nextNum, out next))
stacks.Push(next);
}
// top
else if(input.Contains("top"))
{
if(stacks.Count == 0)
{
cw.AppendLine("-1");
}
else
{
cw.Append(stacks.Peek() + "\n");
}
}
// pop
else if (input.Contains("pop"))
{
if(stacks.Count == 0)
{
cw.AppendLine("-1");
}
else
{
cw.Append(stacks.Pop() + "\n");
}
}
// empty
else if (input.Contains("empty"))
{
if (stacks.Count == 0)
cw.AppendLine("1");
else
cw.AppendLine("0");
}
//size
else if (input.Contains("size"))
{
cw.Append(stacks.Count + "\n");
}
}
Console.WriteLine(cw.ToString());
}
}
}
그래서 Console.WriteLine에 apend한 값을 ToString으로 출력해주도록 하자. 여기서 주의할 점은 stack의 함수를 사용할 경우 Append로 넣어줘야 하며, 그렇게 되면 출력이 옆으로 되기 때문에 역슬래쉬로 한 칸 띄어주도록 하자.
회고
스택에 대해 기초적이면서 다시 한번 상기하는 계기가 되었으며, 시간 초과가 뜨길래 당황했지만 이전에 했던 StringBuilder를 이용하여 해결하게 되었다.