프로그래머스 2단계 : 뒤에 있는 큰 수 찾기 (Java 자바)

문제 설명

 

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

 

 

 

제한사항

 

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

 

입출력 예

 

 

풀이

 

1. Stack<Integer> st를 사용하여 뒷 큰수를 찾기 위한 스택 자료구조를 생성합니다.

2. int[] answer 배열을 생성하여 결과를 저장할 공간을 마련합니다. 이 배열의 초기값은 -1로 설정합니다. -1은 뒷 큰수를 찾지 못한 경우를 나타냅니다.

3. 배열을 뒤에서부터 순회합니다. 이렇게 순회하면서 현재 원소의 뒷 큰수를 찾아나갑니다.

4. 현재 원소를 number 변수에 저장하고, answer[i]를 초기값 -1로 설정합니다.

5. 스택이 비어있지 않을 때까지 반복문을 실행합니다. 반복문 안에서는 스택의 맨 위 원소(top)를 확인합니다.

6. top이 현재 원소 number보다 큰 경우, top을 answer[i]에 저장하고 반복문을 종료합니다. 이렇게 하면 현재 원소의 뒷 큰수를 찾은 것입니다.

7. 스택이 비어있지 않은 경우, 스택의 맨 위 원소를 제거하여 뒷 큰수를 찾지 못한 경우를 처리합니다.

8. 현재 원소 number를 스택에 추가하여 다음 원소의 뒷 큰수를 찾을 준비를 합니다.

9. 모든 원소에 대해 뒷 큰수를 찾은 결과를 반환합니다.

 

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        Stack<Integer> st = new Stack<Integer>(); // 스택을 사용하여 뒷 큰수를 찾기 위한 자료구조를 생성
        
        int[] answer = new int[numbers.length]; // 결과를 저장할 배열 생성
        for (int i = numbers.length - 1; i >= 0; i--) { // 배열을 뒤에서부터 순회
            int number = numbers[i]; // 현재 원소
            answer[i] = -1; // 초기값으로 -1 설정 (뒷 큰수를 찾지 못하는 경우)
            while (!st.empty()) { // 스택이 비어있지 않을 때까지 반복
                int top = st.peek(); // 스택의 맨 위 원소 확인
                if (top > number) { // 스택의 맨 위 원소가 현재 원소보다 큰 경우
                    answer[i] = top; // 현재 원소의 뒷 큰수로 스택의 맨 위 원소 설정
                    break; // 뒷 큰수를 찾았으므로 반복문 종료
                }
                st.pop(); // 스택의 맨 위 원소를 제거 (뒷 큰수를 찾지 못한 경우)
            }
            st.add(number); // 현재 원소를 스택에 추가하여 다음 원소의 뒷 큰수를 찾을 준비
        }
        return answer; // 결과 배열 반환
    }
}