코딩 테스트 [프로그래머스] - 뒤에 있는 큰 수 찾기

문제 링크

스택에 수를 넣고
하나씩 꺼내면서 비교대상과 비교하면서

• 비교대상보다 크면 비교대상을 스택에 넣는다
• 비교대상보다 작으면 스택에서 꺼낸다

를 반복하면
스택 내부는 정렬이 되고, 작은 수가 먼저 나오게 되는 점을 이용해 문제를 풀었다.

---

전체 코드는 다음과 같다

import java.util.*;

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

---

주어진 숫자 갯수만큼 정답 배열을 만들고 배열의 모든 수를 -1로 초기화한다.

        int[] answer = new int[numbers.length];
        for(int i = 0; i < answer.length; i++)
            answer[i] = -1;

숫자의 위치를 저장하는 Stack을 만들고, 첫 위치인 0을 집어넣는다.

        Stack<Integer> stack = new Stack<>();
        stack.add(0);

스택 안의 숫자와 비교를 하기 위해 비교대상의 위치를 나타내는 i를 반복문을 통해 하나씩 증가시킨다.

        for(int i = 1; i < numbers.length; i++){
            ...
        }

비교대상과 스택안의 숫자들을 비교한다.
스택이 빌 때까지 while 문으로 반복하며
스택에서 숫자를 하나 꺼내

• 비교대상보다 크면 깨낸 숫자를 다시 넣고 while 반복문을 종료한다.
• 비교대상보다 작으면 스택에서 꺼내고, 정답에 비교대상을 저장한다.

반복문이 끝나면 비교대상의 뒷큰수도 얻기위해 비교대상도 스택에 집어넣는다.

        for(int i = 1; i < numbers.length; i++){
            while(!stack.isEmpty()){
                int now = stack.pop();
                
                if(numbers[now] < numbers[i]){
                    answer[now] = numbers[i];
                }else{
                    stack.add(now);
                    break;
                }
            }
            
            stack.add(i);
        }

반복문이 끝나면 모든 수의 뒷큰수가 정답 배열에 모두 저장된다.