• Feed
  • Explore
  • Ranking
/
/
    CodingTest

    코딩테스트 준비 - 스택

    혼자서 다시푸는 코딩테스트 준비 일지 - 22
    구현자료구조스택
    B
    Brocolling
    2024.09.19
    ·
    8 min read

    다시푸는 코딩 테스트 준비 일지

    • 응시 사이트 : BOJ

    • 문제 : 10828.스택

    • 사용언어 : C#

    • 난이도 : 중하

    • 풀이시간 : 43m

    • 유형 : 구현, 자료구조, 스택

    문제

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

    명령은 총 다섯 가지이다.

    • 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

    문제 풀이 접근

    문제의 요구사항은 많아보이지만, 스택에 있는 5개의 함수를 만들어서 확인해야하니, 요구사항에 맞춰서 출력해봐라. 라는 문제다.

    크게 어려운 것은 없고, 까다로운 부분은 Push, Pop을 할때 밀어주고 당겨주는 부분이 조금은 까다로울 수 있지만 몇번 디버깅하면 해결할 수 있다.

    문제의 플로우는 딱히 없다.

    스택을 구현하는 문제니까, 개인적으로 제한사항을 두자면 스택 자료구조는 사용하지 말자.

    정답 작성 코드 (C#)

    using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;

/*
 * URL : https://www.acmicpc.net/submit/10828
 */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int loop = Int32.Parse(Console.ReadLine());
            var solutions = new Solution();
            solutions.Prog(loop);

            print.printRet();
        }
    }

    public static class print
    {
        public static List<int> _list = new List<int>();

        public static void printRet()
        {
            for (int i = 0; i < _list.Count; ++i)
                Console.Write(_list[i] + $"\n");
        }
    }

    public class Solution
    {
        const int _arrCount = 10000;
        public int[] _arr = new int[_arrCount];
        public int _count = 0;

        public void Prog(int loop)
        {
            for(int i = 0; i < loop; ++i)
            {
                string[] commandArr = Console.ReadLine().Split(' ');
                string command = commandArr[0];
                

                if (command.Equals("push"))
                {
                    int IntValue = Int32.Parse(commandArr[1]);
                    push(IntValue);
                }
                else if (command.Equals("top"))
                {
                    top();
                }
                else if (command.Equals("size"))
                {
                    size();
                }
                else if (command.Equals("empty"))
                {
                    empty();
                }
                else if (command.Equals("pop"))
                {
                    pop();
                }
                else { }
            }
        }

        private void push(int x)
        {
            for(int i = 1; i <= _count; ++i)
            {
                _arr[i] = _arr[i - 1];
            }// 밀기

            _arr[0] = x;
            _count++;
        }

        public void top()
        {
            if (_count == 0)
            {
                //print._list.Add(-1);
                Console.Write(-1 + $"\n");
            }
            else
            {
                //print._list.Add(_arr[0]);
                Console.Write(_arr[0] + $"\n");
            }
        }

        public void size()
        {
            //print._list.Add(_count);
            Console.Write(_count + $"\n");
        }

        public void empty()
        {
            if(_count == 0)
            {
                //print._list.Add(1);
                Console.Write(1 + $"\n");
            }
            else
            {
                //print._list.Add(0);
                Console.Write(0 + $"\n");
            }
        }

        public void pop()
        {
            if(_count == 0)
            {
                //print._list.Add(-1);
                Console.Write(-1 + $"\n");
            }
            else
            {
                var _popValue = _arr[0];
                _arr[0] = 0;

                for(int i = _count -1; i > 0; --i)
                {
                    _arr[i - 1] = _arr[i];
                    _arr[i] = 0;
                }// 당기기

                _count--;
                //print._list.Add(_popValue);
                Console.Write(_popValue + $"\n");
            }
        }
    }
}

    코드 결과 - 아직 풀지 못함.

    ** 이 문제도 아직 풀이를 하여 결과를 보진 못했다.
    BOJ 사이트에 내가 뭔가 놓치고 있는 부분이 있는것 같다.
    푼 문제마다 1%에서 실패는 문제가 있다는 것 아닐까..

    // 240920 추가

    문제를 풀 수 없어, 질문을 올렸는데 push, pop연산에 대해 O(N) 연산으로 비효율적이고, 일단 출력도 다르다는 피드백을 받았다.

    0번째로 구현하는 것이 아닌 역방향으로 구현하면 해결된다는 피드백을 받아, 코드를 수정하여 해결하였다.

    정답 작성 코드 (C#) - 위 코드에서 push,pop,top 만 다름

    using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;

/*
 * Difficulty : Easy ~ Middle
 * URL : https://www.acmicpc.net/submit/10828
 */


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

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int loop = Int32.Parse(Console.ReadLine());
            var solutions = new Solution();
            solutions.Prog(loop);

            print.printRet();
        }
    }

    public static class print
    {
        public static List<int> _list = new List<int>();

        public static void printRet()
        {
            for (int i = 0; i < _list.Count; ++i)
                Console.Write(_list[i] + $"\n");
        }
    }

    public class Solution
    {
        const int _arrCount = 10000;
        public int[] _arr = new int[_arrCount];
        public int _count = 0;

        public void Prog(int loop)
        {
            for (int i = 0; i < loop; ++i)
            {
                string[] commandArr = Console.ReadLine().Split(' ');
                string command = commandArr[0];


                if (command.Equals("push"))
                {
                    int IntValue = Int32.Parse(commandArr[1]);
                    push(IntValue);
                }
                else if (command.Equals("top"))
                {
                    top();
                }
                else if (command.Equals("size"))
                {
                    size();
                }
                else if (command.Equals("empty"))
                {
                    empty();
                }
                else if (command.Equals("pop"))
                {
                    pop();
                }
                else { }
            }
        }

        private void push(int x)
        {
            _arr[_count] = x;
            _count++;
        }

        public void top()
        {
            if (_count == 0)
            {
                //print._list.Add(-1);
                Console.Write(-1 + $"\n");
            }
            else
            {
                //print._list.Add(_arr[0]);
                Console.Write(_arr[_count-1] + $"\n");
            }
        }

        public void size()
        {
            //print._list.Add(_count);
            Console.Write(_count + $"\n");
        }

        public void empty()
        {
            if (_count == 0)
            {
                //print._list.Add(1);
                Console.Write(1 + $"\n");
            }
            else
            {
                //print._list.Add(0);
                Console.Write(0 + $"\n");
            }
        }

        public void pop()
        {
            if (_count == 0)
            {
                //print._list.Add(-1);
                Console.Write(-1 + $"\n");
            }
            else
            {
                var _popValue = _arr[_count-1];
                _count--;
                //print._list.Add(_popValue);
                Console.Write(_popValue + $"\n");
            }
        }
    }
}

    코드 결과

    until-1403
    - 컬렉션 아티클