[프로그래머스] 2️⃣ 뒤에 있는 큰 수 찾기(JAVA)

💡 문제

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

---

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  • 1 ≤ numbers[i] ≤ 1,000,000

---

입출력 예

numbers result

[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

---

입출력 예 설명

입출력 예 #12의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #29는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

💡 코드

⇒ 스택을 쓰지 않아서 시간 초과로 실패한 코드

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int [numbers.length];
        
        //이중for문을 돌면서 자기 뒤 있는 수 중에서 크고 가까운 값을 max에 임시 저장
        for (int i=0; i<numbers.length; i++){
            int max=0;
            for (int next=i+1; next<numbers.length; next++){
                //큰 수를 발견하면 ? -> max에 임시로 넣어둠
              if (numbers[i]  < numbers[next] )  {
                  max=Math.max(max, numbers[next]); 
                  break;
                }
            }
            if (max==0){
                //나보다 큰 수를 발견하지 못하면 -1을 넣으줌 
                answer[i]=-1;
            }    
            else {
                answer[i]=max;
            }
             // 다음 max를 찾기 위해서 0으로 초기화 
            max=0;
        }

        return answer;
    }
}

⬇️ 완성된 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int [numbers.length];
        
        Stack <Integer> stack = new Stack <>();// 뒤에 있는 수 중에 큰 값을 발견 못하면 스택에 넣음
        Arrays.fill(answer, -1);
        
        for (int i=0; i<numbers.length; i++){
                           while(!stack.isEmpty()  && numbers[stack.peek()]<numbers[i]){
                    answer[stack.pop()]=numbers[i];
                }
                stack.push(i);

        }
        return answer;
    }
}

1. index를 이용하기

2. 비교하는 수보다  큰 수를 발견하지 못하거나 스택이 비어있다면(처음 시작할 때 등) -> push 

3. 비교하는 수 보다 큰 수를 발견했다면 스택 -> pop

💡 보완할 점

비슷한 문제: https://www.acmicpc.net/problem/17298 백준 골드5