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

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

6198번: 옥상 정원 꾸미기

---

• 문제

---

• 문제풀이

 

처음에는 스택을 두개를 만들어서 하나는 배열로 만들어 거꾸로 순서를 만들어 뒤에서부터 비교를 하면 좋을 것 같다고 생각했다. 맨뒤의 빌딩부터 비교하면서 만약 자신보다 더 뒤에있는 빌딩이 더 작다면 카운트를 세어주고 그렇지 않다면 for문을 끝내는 방식을 사용하려고 했다. 하지만 시간초과도 아닌 메모리 초과를 받게 되었다. 구조체가 너무 많아지고 수가 커지면 할당되는 메모리가 커져서 그런 것 같다. 이런 방법으로 살려보려다가 다른 방식으로 결국 변경했다.

using System.Text;

namespace YongYong2
{

    internal class Program
    {
        static void Main(string[] args)
        {
            Stack<int> towerlevel = new Stack<int>();
            Stack<int> check = new Stack<int>();
            long N = int.Parse(Console.ReadLine());
            long count = 0;
            int[] checking = new int[N];
            for (int i = 0; i < N; i++)
            {
                check.Push(int.Parse(Console.ReadLine()));
                checking = check.ToArray();
            }
            while (N-- > 0)
            {
                towerlevel.Push(check.Pop());

                if (towerlevel.Count() == 1)
                {
                    continue;
                }
                else
                {
                    for (long j = towerlevel.Count() - 2; j >= 0; j--)
                    {

                        if (towerlevel.Peek() > checking[j])
                        {
                            count++;

                        }
                        else
                        {

                            break;
                        }

                    }

                }
            }

            Console.Write(count);
        }
    }
}

노력의 흔적

틀리면 틀리다고 나오는 걸 보면 답은 맞을지도...?

 

그래서 그냥 싹 갈아엎고 다른 방식으로 접근했다.

스택을 넣어주면서 이전의 빌딩보다 높은 빌딩이 나온다면 스택에서 없애주고 빌딩의 개수를 세어준다.

 

코드 과정

1. 10이 들어가면 while문에 걸리지 않고 스택에 들어가게 된다.

스택: 10

카운트: +0

 

2. 3이 들어가면 역시 while문에 들어가지않고 push된다.

스택: 10 3

카운트: +0+1

 

3. 7이 들어가면 while문에 걸리게 되고 10이 나올때까지 pop을 해주고 push된다.

스택: 10 3 -> 10 7

카운트 +0+1+1

 

4. 4가 들어가면 while에 걸리지 않고 스택에 들어간다.

스택: 10 7 4

카운트+0+1+1+2

 

5. 12가 들어가면 while문에 걸리게 되고 pop을 해주게 된다.

스택: 10 7 4 -> 12

카운트+0+1+1+2+0

 

6. 2가 들어가면 while에 걸리지 않고 스택에 넣어준다.

스택: 12 2

카운트+0+1+1+2+0+1=5

---

• 코드 1

using System.Text;

namespace YongYong2
{
    
    internal class Program
    {
        public static Stack<int> stack = new Stack<int>();
        public static long answer = 0;
        public static void Solution(int N)
        {
           
             while (stack.Count() != 0 && stack.Peek() <= N)
             {
                 stack.Pop();
             }
             answer += stack.Count();
             stack.Push(N);
            
        }
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            for(int i = 0; i < N; i++)
            {
                int input=int.Parse(Console.ReadLine());
                Solution(input);
            }
            Console.WriteLine(answer);
        }
    }
}

---

• 후기

항상 어렵게 풀기보다 어려운걸 쉽게 풀려고 노력하는게 가장 중요한 것 같다.