Level 2: 뒤에 있는 큰 수 찾기, Stack 자료 구조를 사용한 풀이

참고 문서

• Programmers: 뒤에 있는 큰 수 찾기

이 문서의 내용

문제 풀이: 단순 반복문을 사용한 해결

배열의 전체 원소를 순회하며 문제를 해결합니다.
구현은 간단하지만 중첩 for 반복문으로 인해 일부 테스트케이스에서 timeout 오류가 발생합니다.

public class Solution
{
	public int[] solution(int[] numbers) 
	{
		for (int i = 0; i < numbers.length; ++i) 
		{
			int src, trg;
			src = trg = numbers[i];
			for (int j = i; j < numbers.length; ++j) 
			{
				trg = numbers[j];
				if (src < trg) {
					break;
				}
			}

			numbers[i] = (src < trg) ? trg : -1;
		}

		return numbers;
	}
}

코드		비고
Line 9:15	for (j = i; j < numbers.length; ++j) { }	원소의 뒤에 이어지는 원소 중 자신보다 크면서 가장 가까운 값을 찾습니다.

문제 풀이: Stack 자료 구조를 사용한 풀이

배열의 가장 끝에서부터 전체 원소를 순회하며 문제를 해결합니다. 자신보다 크면서 가장 가까운 값을 찾는 과정은 Stack으로 구현 할 수 있습니다.

• Stack에서 원하는 값을 찾을때까지 또는 Stack의 원소가 남아있는 동안 반복합니다.
• 원하는 값을 찾지 못하면 POP합니다(예시의 7과 8).
• 원하는 값을 찾으면 PEEK합니다(예시의 10).
• 과정이 끝나면 현재 값을 ADD합니다(예시의 9, Next Stack).
• 문제의 제약 사항에서 원하는 값을 찾지 못하면 -1을 사용합니다.

예시에서 과정이 끝나면 9가 ADD됩니다. 그리고 과정이 진행되면서 비교 값보다 작은 7 8은 POP됩니다.

결과적으로 Stack을 사용해 미래에 참조할 필요없는 원소는 삭제하면서 오름차순으로 정렬된 상태를 유지합니다.

전반적인 과정은 다음과 같습니다.

전체 구현 코드는 다음과 같습니다.

import java.util.*;

public class Solution
{
	public int[] solution(int[] numbers) 
	{
		Stack<Integer> stack = new Stack<>();
		for (int i = numbers.length - 1; i >= 0; --i)
		{
			int curr = numbers[i];
			int prev = -1;
			while (!stack.isEmpty()) 
			{
				if (curr < stack.peek()) {
					prev = stack.peek();
					break;
				}
				
				stack.pop();
			}
			
			numbers[i] = prev;
			stack.add(curr);
		}
		
		return numbers;
	}
}

코드		비고
Line 8	for (i = numbers.length; i >= 0; --i)	배열의 가장 끝에서부터 전체 원소를 순회합니다.
Line 11	prev = -1	문제의 제약사항에 따라서 원하는 값을 찾지 못하면 -1을 사용합니다.
Line 14:17	if (curr < stack.peek()) { }	원하는 값을 찾으면 Stack 순회를 종료합니다.
Line 19	stack.pop()	원하는 값을 찾지 못할때마다 Stack을 POP합니다.
Line 23	stack.add()	원소 하나가 처리되면 Stack에 ADD합니다.