[17298] - 오큰수

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

17298번: 오큰수

접근 방식

2중 반복문으로 현재가 i라면 i+1부터 끝까지 돌리면서 현재보다 큰 값이 나오면 그 값stringbuilder에 넣고 탈출, 큰 값이 없으면 -1 넣어주었는데 38%에서 시간초과가 떴다.

그래서 어차피 수의 크기는 의미가 없고 현재보다 우측이 크면 되니 가장 우측부터 돌려서 하나하나 비교하기로 했다.

- stb.insert를 사용했다가 시간초과가 떠서 배열로 바꿔 줌.

 

문제 풀이

1. 가장 우측부터 돌린다. 가장 우측은 스택도 비어있고, 오른쪽에 자신보다 큰게 없으니 -1, 스택에 삽입

2. 만약 스택이 차있고 꼭대기가 현재값 보다 크면 탈출, 작으면 빼기 -> 스택의 꼭대기는 오른쪽 가장 왼쪽 값이니 일단 현재값보다 크면 그냥 그거 출력해주면 된다.

• ex) 현재가 3, 스택에 2, 7이 들어있으면 2는 빠지고 7이 남기 때문

3. 스택에 현재값 넣고 반복

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Gold
{
    class _17298
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Stack<int> stack = new Stack<int>();
            int[] ans = new int[n];

            for(int i = n-1; i>=0; i--)
            {
                //스택에 들어있으면
                while (stack.Count > 0)
                {
                    //만약 스택 top이 지금보다 같거나 작으면 뽑기
                    if (stack.Peek() <= arr[i])
                        stack.Pop();
                    else //아니면 탈출
                        break;
                }

                //스택이 비었다면 현재보다 우측에 큰게 없으니까 -1
                if (stack.Count == 0)
                    ans[i] = -1;
                else //아니면 가장 우측 왼쪽꺼가 꼭대기에 있음
                    ans[i] = stack.Peek();

                stack.Push(arr[i]);
            }
            Console.WriteLine(string.Join(" ", ans));
        }
    }
}