[programmers] 뒤에 있는 큰 수 찾기 - Java

정수 배열 numbers에서 각 원소에 대해 자신보다 뒤에 있는 가장 가까운 큰 수를 찾는 문제를 다루고 있다. 스택을 사용하여 효율적으로 해결하며, 각 원소를 처리하는 동안 현재 숫자보다 작거나 같은 숫자는 스택에서 제거한다. 최종적으로 시간 복잡도는 O(n)이다.
DriedPollack's avatar
Sep 16, 2024
[programmers] 뒤에 있는 큰 수 찾기 - 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]
 

solution.java

import java.util.*; class Solution { public int[] solution(int[] numbers) { int n = numbers.length; int[] result = new int[n]; Stack<Integer> stack = new Stack<>(); for (int i = n - 1; i >= 0; i--) { // 스택에서 현재 숫자보다 작거나 같은 요소를 pop while (!stack.isEmpty() && stack.peek() <= numbers[i]) { stack.pop(); } // 스택이 비어 있으면 오른쪽에 더 큰 숫자가 없음 if (stack.isEmpty()) { result[i] = -1; } else { result[i] = stack.peek(); } // 현재 숫자를 스택에 push stack.push(numbers[i]); } return result; } }
 

핵심 키워드

  • 스택을 사용해서 수를 저장하면 다음으로 큰 숫자를 효율적으로 찾을 수 있다.
  • 오른쪽에서 왼쪽으로 배열을 처리함으로써 스택을 사용하여 방문한 숫자를 추적할 수 있다.
  • 각 요소를 처리하는 동안 현재 숫자보다 작거나 같은 숫자는 나중에 방문할 숫자에 대해 큰 수가 될 수 없기 때문에 스택에서 요소를 pop한다.
 

결론!

스택을 사용해서 해당 문제를 풀게 되면 스택에서 최대 한 번 push되고 pop되므로 시간 복잡도는 O(n)이 된다.
 
Share article

More articles

See more posts

👨🏻‍💻DriedPollack's Blog