[154539] 뒤에 있는 큰 수 찾기

✔ 뒤에 있는 큰 수 찾기

[프로그래머스 154539]

문제 분석하기

스택을 이용해 인덱스를 집어 넣으며 자신 보다 큰 값이 들어올 경우 이를 저장하며 빼도록 함

만약 끝까지 자신보다 큰 값이 없을 경우 -1을 반환하도록 함

 

예) [9, 1, 5, 3, 6, 2]

i	stack	numbers[stack.peek()] < numbers[i]	answer
1	0	9 < 1 (X)	[0, 0, 0, 0, 0, 0]
2	1 0	1 < 5 (O) 9 < 5 (X)	[0, 5, 0, 0, 0, 0]
3	2 0	5 < 3 (X) 9 < 3 (X)	[0, 5, 0, 0, 0, 0]
4	3 2 0	3 < 6 (O) 5 < 6 (O) 9 < 6 (X)	[0, 5, 6, 6, 0, 0]
5	4 0	6 < 2 (X) 9 < 2 (X)	[0, 5, 6, 6, 0, 0]
[-1, 5, 6, 6, -1, -1]

손으로 풀어보기

1. 스택을 이용해 인덱스를 집어 넣으며 자신 보다 큰 값이 들어올 경우 이를 저장하고 빼냄
2. 끝까지 자신보다 큰 값이 없을 경우 -1을 반환

슈도코드 작성하기

numbers(정수 배열)
answer(모든 원소에 대한 뒷 큰수들을 차례로 담은 배열)
stack(정수를 담을 스택)
stack에 첫 번째 정수의 인덱스인 0 저장
for(i -> 1부터 numbers만큼) {
    while(스택이 비어있지 않으면서 현재 스택이 바라보고 있는 값보다 numbers의 값이 크다면) 
        answer[stack.pop]에 numbers[i] 저장
    stack에 정수의 인덱스인 i 저장
}
while(stack이 비어 있지 않는 동안) 
    answer[stack.pop]에 -1 저장
answer 반환

코드 구현하기

/**
 * 154539) 뒤에_있는_큰_수_찾기
 */
public class L095_154539 {
    // numbers(정수 배열)
    public int[] solution(int[] numbers) {
        // answer(모든 원소에 대한 뒷 큰수들을 차례로 담은 배열)
        int[] answer = new int[numbers.length];
        // stack(정수를 담을 스택)
        Stack<Integer> stack = new Stack<>();
        // stack에 첫 번째 정수의 인덱스인 0 저장
        stack.push(0);
        for (int i = 1; i < numbers.length; i++) {
            // 스택이 비어있지 않으면서 현재 스택이 바라보고 있는 값보다 numbers의 값이 크다면
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i])
                // answer[stack.pop]에 numbers[i] 저장
                answer[stack.pop()] = numbers[i];
            // stack에 정수의 인덱스인 i 저장
            stack.push(i);
        }
        // stack이 비어 있지 않는 동안
        while (!stack.isEmpty())
            // answer[stack.pop]에 -1 저장
            answer[stack.pop()] = -1;
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L095_154539 solution = new L095_154539();

        int[] numbers = { 2, 3, 3, 5 };

        int[] result = solution.solution(numbers);

        System.out.println(Arrays.toString(result));
    }
}