[백준/C# (.NET)] 10828번 스택
백준 온라인 저지 / 10828번 스택
https://www.acmicpc.net/problem/10828
10828번: 스택
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
- 사용언어 : C# (.NET)
- 알고리즘 : 자료 구조, 스택
C#코드
1. 문제 정리(여담)
이번 문제는 테스트 케이스 값을 받아와 그 값만큼 명령어를 받아오는 문제이다.
일단 나에게 자료구조를 정확히 아냐고 물어본다면 대답은 No이다.
정확하게 모른다. 그래서 C로 구현을 못한다 뭐 구글링 하면서 풀면 되긴 하겠다만 ㅋㅋㅋㅋ (학교에서 뭐 배우겠지..)
이 문제를 C로 구현하려면 아마 정확히 자료구조를 알고 풀어야 할 것이다.
아마 C++ 에는 push pop 같은 스택 함수가 있는 걸로 아는데 C로는 하나하나 다 만들어서 사용해야 하기 때문이다...
이제부터 C로만 문제를 풀겠다던 나 놈은 어딘가로 사라지고 나태한 웅이만 남게 되었다..
물론 지금의 나라면 C나 C++로 풀라고 했을 거다. C#으로 풀다가 시간 초과를 몇 번을 본지.. XX;;
어쨌든 지금 나는 class 2를 밀고 class 3로 가고 싶지만 그걸 넘으려면 스택과 큐 공부가 무조건 필요하기 때문에 방학 안에 스택 큐를 조금 정리해보려고 한다. 알고리즘도 마찬가지다.
클래스 2에서 가장 기본 되는 스택 문제를 알려주는데 이걸 넘어야 다른 코테도 문제들도 풀 수 있을 것이다.
잡설이 너무 길었고 문제를 다시 보자.
| 스택 명령어 | description |
| push X | 정수 X를 스택에 넣는 연산이다. |
| pop | 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. |
| size | 스택에 들어있는 정수의 개수를 출력한다. |
| empty | 스택이 비어있으면 1, 아니면 0을 출력한다. |
| top | 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. |
글로만 봐서는 뭘 빼고 넣고 지지고 볶고 하는 거 같은데 스택에 대해서 간단하게 짚고 넘어가 보자.
2. 스택이란 무엇일까?
문제 이름부터 스택인데 스택을 모르고 그냥 지나칠 순 없는 거다..
스택에 대해서 집중적으로 자세하게 파고드는 건 프로그래밍 노트에서 하도록 하고, 간단하게만 알아보자
화질이 구린 건 좀 미안합니다..
Stack은 책이 쌓인 모양을 보고 스택을 떠올리면 된다.
먼저 쌓은 책을 들어 올려야 다음 책을 들어 올릴 수 있는 그런 구조란 말이다.
책 = 데이터라고 생각할 때
책을 쌓을 때는 Push()를 사용하고
책을 위로 들 때는 Pop()을 사용하는 것이다.
두 개다 가장 위에 있는 것을 사용하기에 후입 선출 즉 LIFO라고 부른다고 한다 ㅇㅇ...
다음에 스택에 대해서 자세히 살펴보고 이 정도만 알아도 이번 문제 푸는 데는 문제가 없다.
더 자세히 알아보고 싶다면
Stack 클래스 (System.Collections)
제네릭이 아닌 개체의 간단한 LIFO(Last In First Out: 마지막에 들어간 것부터 사용) 컬렉션을 나타냅니다.Represents a simple last-in-first-out (LIFO) non-generic collection of objects.
docs.microsoft.com
여기서 더 읽어보도록 해라.. 난 다음에...
3. C#에서의 스택
C#에서 스택을 사용할 건데 그다지 어렵지 않다. 우리 아까 문제에서 총 5개의 명령어가 있었다.
Push, Pop, size, empty, top
일단 C# 공식 문서를 읽어보자.
네임스페이스가 System.Collections니깐 가져오면 되는데 우린 여기서 Stack을 형 변환해야 하는
Stack <T>를 사용해야 되기 때문에 System.Collections.Generic을 가져오도록 하자 어셈블리는 아마 C#에 내장되어 있을 거다.
Generic을 사용하는 게 중요하다. 일단 스택이나 current 스택 사용하면서 왜 안되냐고 화내는 짓은 하지 마라.
using System.Collections.Generic;
Stack<int> stack = new();
이런 식으로 int형 스택을 만들고 이름을 stack으로 했다. (대문자로 하면 예약어 오류 나니깐 조심)
그리고 그냥 문제에서 하라는 대로 했다.
var A = int.Parse(Console.ReadLine());
Stack<int> stack = new();
for (int i = 0; i < A; i++)
{
string[] input = Console.ReadLine().Split(' ');
//값을 한 줄씩 받아오는데 만약 공백으로 띄워져있다면 배열로 나눠짐.
//예시: push 3 일 때 input[0]=push 이고 input[1]=3 이런 식으로 받아옴
if(input[0] == "push")
{
stack.Push(int.Parse(input[1]));
}
else if(input[0] == "pop")
{
if (stack.Count == 0)
{
Console.WriteLine("-1");
}
else
{
Console.WriteLine(stack.Pop());
}
}
else if(input[0] == "size")
{
Console.WriteLine(stack.Count);
}
else if(input[0] == "empty")
{
if (stack.Count == 0)
{
Console.WriteLine("1");
}
else
{
Console.WriteLine("0");
}
}
else if(input[0] == "top")
{
if (stack.Count == 0)
{
Console.WriteLine("-1");
}
else
{
Console.WriteLine(stack.Peek());
}
}
}
전부 stack.Count를 사용해서 풀면 된다.
push X를 받아오면 정수 X로 스택에 넣어주고
pop을 받아오면 만약 스택 안에 값이 없을 경우 -1을 출력하고 값이 있을 경우 가장 위에 있는 값을 빼고 그 수를 출력
size를 받아오면 스택에 들어 있는 정수의 개수를 출력
empty는 스택을 확인한 후 없으면 1 아니면 0을 출력해주고
top은 스택 가장 위에 있는 정수를 출력해주고 만약에 값이 없다면 -1을 출력해주는 걸 모두 if else 문을 사용해서 넣었다.
자 그럼 문제 끝일까?
제출해보자.
아니 먼가 퍼센트가 안 올라가고 멈춰 있길래 불안했는데 역시나 역시나...
그래서 시간 초과가 뜨는 이유를 찾아봤다..
아무리 봐도 모르겠더라, 그래서 우리 C# 선배님들의 답을 살짝 봤더니 열자마자 알았다.
이 문제는 Console.WriteLine을 쓰는 순간 시간초과가 뜰 수밖에 없는 문제다.
4. StringBuilder
심지어 이건 학교 책 어디선가 봤던 내용인데,,
어쨌든 다시 찾아봤더니 string + string과 append로 string을 더하는 것은 차이가 있었다.
바로 메모리의 낭비였다.
string + string은 문자열을 조합할 때 새로운 string 객체가 생성되면서 이전 문자의 객체들은 쓰레기 값으로 남는다고 한다.
+연산을 한 번 할 때마다 string 객체 메모리가 뭐 낭비된다는데 어쨌든 이 문제에선 이 것 때문에 streambuilder을 사용해 주어야 한다.
Console.write와 string 대신 stringbuilder와 appendline을 써주면 해결된다.
C#은 참 편한데 뭔가 이런 데서 별로란 말이지.. ㅠ
5. 완성 코드
using System;
using System.Collections.Generic;
using System.Text;
namespace boj
{
class Program
{
static void Main(string[] args)
{
var A = int.Parse(Console.ReadLine());
Stack<int> stack = new();
StringBuilder sw = new();
for (int i = 0; i < A; i++)
{
string[] input = Console.ReadLine().Split(' ');
if(input[0] == "push")
{
stack.Push(int.Parse(input[1]));
}
else if(input[0] == "pop")
{
if (stack.Count == 0)
{
sw.AppendLine("-1");
}
else
{
sw.Append(stack.Pop() + "\n");
}
}
else if(input[0] == "size")
{
sw.Append(stack.Count + "\n");
}
else if(input[0] == "empty")
{
if (stack.Count == 0)
{
sw.AppendLine("1");
}
else
{
sw.AppendLine("0");
}
}
else if(input[0] == "top")
{
if (stack.Count == 0)
{
sw.AppendLine("-1");
}
else
{
sw.Append(stack.Peek() + "\n");
}
}
}
Console.WriteLine(sw.ToString());
}
}
}