백준 C# - 17298 +) 풀이

시간초과

문제를 보고 어 쉽네? 이렇게 풀다가 시간초과가 나왔다.

int n = int.Parse(Console.ReadLine());
string line = Console.ReadLine();
string[] token = line.Split(' ');

int[] A = new int[n]; 
StringBuilder answer = new StringBuilder();

for (int i = 0; i < n; i++)
{
    A[i] = int.Parse(token[i]); 
}
int[] NGE = new int[n];

for (int i = 0; i < n; i++)
{
    int max = -1; 
    for (int j = i + 1; j < n; j++)
    {
        if (A[i] < A[j])
        {
            max = A[j];
            break;
        }
    }
    answer.Append(max);
    if (i < n - 1)
        answer.Append(" ");
}

Console.Write(answer.ToString());

---

스택으로 풀어야한다!

위의 코드 같은 경우 배열 크기만큼 계속 반복되는데 스택을 사용하게되면 스택크기만큼만 반복하면 된다. 그러므로 위의 코드보다 아래 코드가 더 성능이 좋다.

 

주의

stack에 Push되는 것은 A의 원소가 아니라 i값이어야 한다. 

int n = int.Parse(Console.ReadLine());
string line = Console.ReadLine();
int[] A = Array.ConvertAll(line.Split(), int.Parse);
int[] NGE = new int[n];
Stack<int> stack = new Stack<int>();

for(int i = 0; i < n; i++)
{
    while(stack.Count > 0 && A[i] > A[stack.Peek()])
    {
        NGE[stack.Pop()] = A[i];
    }
    stack.Push(i);
}
while(stack.Count > 0)
{
    NGE[stack.Pop()] = -1;
}
Console.WriteLine(string.Join(" ", NGE));