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

다른 사람들과 마찬가지로 for문 2개를 사용했더니 뒤에 4개는 시간초과로 실패ㅜ

 

문제의 핵심은 stack으로 접근..! 

numbers 배열의 뒤에서부터 접근하여 stack에 쌓고 해당 수와 비교하여 삭제하고 반복하면 된다.

stack은 후입선출 방식으로 한쪽 끝에서만 데이터를 삽입하고 삭제 → 즉 뒤의 숫자들의 가까운 순으로 비교할 수 있음

peek()	최근에 추가된 맨 뒤에 있는 데이터를 반환
pop()	최근에 추가된 맨 뒤에 있는 데이터를 삭제
push()	데이터 추가

 

예시 1

numbers = [2, 3, 3, 5]

answer   = [  ,   ,   ,   ]

stack      = [ ]

 

 

index = 3

numbers = [2, 3, 3, 5]

stack이 비어있는지 확인(비어있음) → answer의 해당 배열에 -1 대입 answer = [  ,   ,   , -1]

stack에 numbers의 숫자를 push → stack = [ 5 ]

 

index = 2

numbers = [2, 3, 3, 5]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (3보다 5가 크므로 answer의 배열에 5 대입 )

answer = [  ,   ,  5, -1]

stack에 numbers의 숫자를 push → stack = [ 5, 3 ]

 

index = 1

numbers = [2, 3, 3, 5]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (3과 3이 같으므로 pop) stack = [ 5 ]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (3보다 5가 크므로 answer의 배열에 5 대입 )

answer = [  ,  5,  5, -1]

stack에 numbers의 숫자를 push → stack = [ 5, 3 ]

 

index = 0

numbers = [2, 3, 3, 5]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (2보다 3이 크므로 answer의 배열에 3 대입 )

answer = [3,  5,  5, -1]

 

 

예시 2

numbers = [9, 1, 5, 3, 6, 2]

answer   = [  ,   ,   ,   ,   ,   ]

stack      = [ ]

 

 

index = 5

numbers = [9, 1, 5, 3, 6, 2]

stack이 비어있는지 확인(비어있음) → answer의 해당 배열에 -1 대입 answer = [  ,   ,   ,   ,   , -1]

stack에 numbers의 숫자를 push → stack = [ 2 ]

 

index = 4

numbers = [9, 1, 5, 3, 6, 2]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (6보다 2가 작으므로 pop) stack = [ ]

stack이 비어있는지 확인(비어있음) → answer의 해당 배열에 -1 대입 answer = [  ,   ,   ,   , -1, -1]

stack에 numbers의 숫자를 push → stack = [ 6 ]

 

index = 3

numbers = [9, 1, 5, 3, 6, 2]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (3보다 6이 크므로 answer의 배열에 6 대입 )

answer = [  ,   ,   ,  6, -1, -1]

stack에 numbers의 숫자를 push → stack = [ 6, 3 ]

 

index = 2

numbers = [9, 1, 5, 3, 6, 2]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (5보다 3이 작으므로 pop) stack = [ 6 ]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (5보다 6이 크므로 answer의 배열에 6 대입 )

answer = [  ,   ,  6,  6, -1, -1]

stack에 numbers의 숫자를 push → stack = [ 6, 5 ]

 

index = 1

numbers = [9, 1, 5, 3, 6, 2]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (1보다 5가 크므로 answer의 배열에 5 대입 )

answer = [  ,  5,  6,  6, -1, -1]

stack에 numbers의 숫자를 push → stack = [ 6, 5, 1 ]

 

index = 0

numbers = [9, 1, 5, 3, 6, 2]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (9보다 1이 작으므로 pop) stack = [ 6, 5 ]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (9보다 5이 작으므로 pop) stack = [ 6 ]

stack이 비어있는지 확인(비어있지 않음) → stack의 peek(마지막 값)과 비교 (9보다 6이 작으므로 pop) stack = [  ]

stack이 비어있는지 확인(비어있음) → answer의 해당 배열에 -1 대입 answer = [-1,  5,  6,  6, -1, -1]

 

 

• 우선 정답을 저장할 answer 배열과 stack을 선언
• for문은 numbers의 index를 뒤에서 부터 시작하여 1씩 줄임
• stack이 비어있을 때 까지 비어있는지 확인하므로 while (!stack.empty()) 조건을 걸어줌
• stack의 마지막 값과 비교 numbers[i] 보다 작거나 같으면 pop한다.
  → 나중에 numbers[i] 값이 push 되므로 numbers[i] 보다 작거나 같은 값이 stack에 남아있으면 numbers[i] 값이 제껴졌을때 같이 제껴짐. 따라서 stack은 numbers 뒤의 수 기준 오름차순 되는 내역만 stack 기준 내림차순으로 저장
  예시 )
  numbers = [6, 3, 4, 2] 일 때
  stack = [2, 4, 3]일 경우 6과 3을 비교(작음) → 6과 4를 비교(작음) → 6과 2를 비교(하지 않아도 됨 어차피 2는 4보다 작아서 6보다 작음)
  따라서 stack = [4, 3]로 비교 가능
• stack의 마지막 값이 numbers[i] 보다 크면 answer[i]에 해당 값을 대입
  stack이 비어있으면 answer[i]에 -1 대입
• answer[i]에 값을 대입하면 stack에 numbers[i]값을 push

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = numbers.length-1; i >= 0; i--) {
            while (!stack.empty()) {
                if (stack.peek() <= numbers[i]) {
                    stack.pop();
                } else {
                    answer[i] = stack.peek();
                    break;
                }
            }

            if (stack.empty()) {
                answer[i] = -1;
            }
            stack.push(numbers[i]);
        }
        return answer;
    }
}