[프로그래머스] 뒤에 있는 큰 수 찾기

문제

첫번째 시도

for (int i = 0; i < numbers.Length; i++)          
	{
     	for (int j = i + 1; j < numbers.Length; j++)
        {
         	if (numbers[j] <= numbers[i]) continue;
            int n = numbers[j] - numbers[i];            // J가 더 큰 상태

             answer[i] = numbers[j]; 
             break;

          }

          if (answer[i] == 0)
          answer[i] = -1;
     }

위와 같이 이중 for 문으로 배열을 정렬하니 몇몇 케이스에서 시간 초과가 났다.

알고리즘

문제를 찾기 위해 찾아본 알고리즘은 Stack

하지만 stack를 또 배열처럼 사용하고 있었다..

문제

나의 문제는 stack안의 value를 배열의 인덱스가 아닌 배열 값을 저장하고 있었다.
그래서 같은 값일 때의 예외처리가 되지 않으며 answer 배열의 값을 할당할때 어려움이 있었다.

또한 stack의 이론만 알고 있을 뿐 어떻게 사용해야 하는지 모르고 있다.
한 사이클 후 스택을 매번 초기화 해주고 있었는데, Pop을 이용해서 값을 모두 호출하면 더 쉬웠다.

정답

            Stack<int> stack = new Stack<int>();
            for (int i = 0; i < numbers.Length; i++)
            {
                while (stack.Count > 0 && numbers[stack.Peek()] < numbers[i])
                {
                    answer[stack.Pop()] = numbers[i];  // 현재 원소보다 작은 원소들의 결과를 갱신
                }
                stack.Push(i);
                answer[i] = -1;  // 초기화
            }

stack을 사용하면서 뒤에 있는 큰 수가 나올 때 까지 순회하는 로직이다.
top value가 현재 index value 보다 작으면 스택에서 pop 하여 인덱스를 결정할 수 있다.