[백준/C# (.NET)] 10828번 스택

 

백준 온라인 저지 / 10828번 스택

https://www.acmicpc.net/problem/10828

10828번: 스택

 

 

• 사용언어 : 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. 스택이란 무엇일까?

 

문제 이름부터 스택인데 스택을 모르고 그냥 지나칠 순 없는 거다.. 

스택에 대해서 집중적으로 자세하게 파고드는 건 프로그래밍 노트에서 하도록 하고, 간단하게만 알아보자

 

Open4Tech.com에서 발췌

화질이 구린 건 좀 미안합니다.. 

Stack은 책이 쌓인 모양을 보고 스택을 떠올리면 된다.

 

먼저 쌓은 책을 들어 올려야 다음 책을 들어 올릴 수 있는 그런 구조란 말이다.

책 = 데이터라고 생각할 때

책을 쌓을 때는 Push()를 사용하고 

책을 위로 들 때는 Pop()을 사용하는 것이다. 

 

두 개다 가장 위에 있는 것을 사용하기에 후입 선출 즉 LIFO라고 부른다고 한다 ㅇㅇ... 

다음에 스택에 대해서 자세히 살펴보고 이 정도만 알아도 이번 문제 푸는 데는 문제가 없다.

 

더 자세히 알아보고 싶다면

 

C# 스택 클래스 DOC

Stack 클래스 (System.Collections)

나무 위키 스택 DOC

 

여기서 더 읽어보도록 해라.. 난 다음에...

 

 

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());
        }
    }
}