[프로그래머스] 뒤에 있는 큰 수 찾기 - Lv.2

프로그래머스 154539번 문제 "뒤에 있는 큰 수 찾기" Lv.2 - 파이썬, 자바

[프로그래머스] 뒤에 있는 큰 수 찾기 Lv.2 - [파이썬/python] [자바/java]

 

 

---

💻 문제 설명

 

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

---

🚨 제한사항

 

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

---

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

[Python] 파이썬 코드

def solution(numbers):

   

    # -1로 원소 채우기

    result = [-1] * len(numbers)

   

    # 스택

    stack = []

   

    # 뒤에서부터 검사

    for i in range(len(numbers)-1, -1, -1):

       

        # stack이 비어있지 않고

        # 현재 숫자(numbers[i])가 stack의 맨 위 원소보다 크거나 같으면

        # 현재 숫자(numbers[i])가 뒤에 숫자보다 크므로 stack 맨 위 원소 삭제

        while stack and numbers[i] >= stack[-1]:

            stack.pop()

       

        # stack이 비어있지 않은 경우

        # 바로 뒤에 있는 큰 수를 찾았으니 result[i] 대입

        if stack:

            result[i] = stack[-1]

       

        # stack에 현재 숫자 추가

        stack.append(numbers[i])

   

    return result

 

 

 

[Java] 자바 코드

import java.util.Stack;
import java.util.Arrays;

class Solution {
    public int[] solution(int[] numbers) {

        // -1로 원소 채우기
        int[] result = new int[numbers.length];
        Arrays.fill(result, -1);

        // 스택
        Stack<Integer> stack = new Stack<Integer>();

        // 뒤에서부터 검사
        for(int i = numbers.length-1; i>-1; i--){

            // stack이 비어있지 않고
            // 현재 숫자(numbers[i])가 stack의 맨 위 원소(stack.peek())보다 크거나 같으면
            // 현재 숫자(numbers[i])가 뒤에 숫자보다 크므로 stack 맨 위 원소 삭제
            while (!stack.empty() && numbers[i] >= stack.peek()){
                stack.pop();
            }

            // stack이 비어있지 않은 경우
            // 현재 숫자(numbers[i])의 바로 뒤에 큰 수를 찾았으므로
            // result[i]에 대입
            if(!stack.empty()){
                result[i] = stack.peek();
            }

            // stack에 현재 숫자(numbers[i]) 추가
            stack.push(numbers[i]);
        }

        return result;
    }
}

 

 

 

---

🏳‍🌈 테스트 결과

 

 

[Python] 파이썬 - 테스트 결과	[Java] 자바 - 테스트 결과