[백준] 6198번 : 옥상 정원 꾸미기 [C#]

며칠전 올린 탑 문제와 비슷한 문제이다.

탑 문제는 가장 가까운 신호를 수신하는 탑의 번호를 출력하는 거라면

이번 문제는 한 탑보다 큰 탑이 올때 까지의 모든 탑(아파트) 의 개수를 구해서 더하여 출력하는 문제이다.

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _6198_boj boj = new _6198_boj();
 
            boj.boj_6198();
 
        }
    }
        internal class _6198_boj
    {
        public void boj_6198()
        {
            int n = int.Parse(Console.ReadLine());
            Stack stack = new Stack(n);
 
            string[] input = new string[n];
            for (int i = 0; i < n; i++)
                input[i] = Console.ReadLine();
 
            long result = 0;
 
            for (int i = 0; i < n; i ++)
            {
                while (stack.top >= 0 && int.Parse(input[int.Parse(stack.Peek())]) <= int.Parse(input[i]))
                {
                    stack.Pop();
                }
 
                result += stack.size;
                stack.Push(i.ToString());
 
            }
            Console.WriteLine(result);
        }
    }
    public class Stack
    {
        public string[] stack;
        public int top = -1;
        public int size = 0;
        public Stack(int n)
        {
            stack = new string[n];
        }
        public void Push(string data)
        {
            if (top != stack.Length - 1)
            {
                top += 1;
                stack[top] = data;
                size++;
            }
        }
        public string Pop()
        {
            string result = null;
            if (top != -1)
            {
                result = stack[top];
                stack[top--] = null;
                size--;
            }
 
            return result;
        }
        public string Peek()
        {
            string result = null;
            if (top != -1)
                result = stack[top];
 
            return result;
        }
    }
}
 
 

 

입력받은 배열의 0번지부터 n - 1번지까지 돌아가며 스택의 맨 위값과 비교하여 같거나 작다면 자신보다 작은 값이 나올때까지 계속 pop해주었다.

pop을 모두 수행 한 이후 (stack이 모두 비게됨 / stack의 맨 위값이 현재 배열의 값보다 큼)

남은 스택의 원소 만큼 결과값에 넣어 주었다. (여기서는 stack.size로 따로 변수를 만들어 주었으나, stack.top + 1을 사용하면 좋을 듯 하다.)

(이 과정은 현재 아파트의 옥상을 볼 수 있는 아파트의 수를 구하는 과정이다.)

마지막으로 현재 아파트의 높이를 가리키는 주소를 스택에 넣어주고 다음 회차로 진행해 주었다.

또한 주어지는 결과값이 매우 크기때문에 (단적인 예로 799,999 + 799,998 + 799,997 .... + 1) 결과를 저장할 변수를 int형으로 하면 오버플로우로 인한 오류가 난다.

그렇기 때문에 long형을 사용해야 한다.