문제 설명 및 요구사항#

• int[] 배열 numbers
• 뒷 큰수 : 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수

모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 리턴해야 한다.

입/출력 예시#

• 예제 1
  • 우선 numbers 배열의 맨 뒤의 원소부터 확인하자. 항상 마지막 원소의 result 값은 -1이다.
  • 이 후, 배열을 거꾸로 순회하면서 뒤에 있는 원소와 비교하게 될 것이다.
    • 3 (numbers[2])은 현재 수와 가장 최근의 뒷 수인 5 (numbers[3])를 비교한다.
    • 3 (numbers[1])은 현재 수와 가장 최근의 뒷 수 (numbers[2]), 가장 최근의 뒷 큰수 (numbers[3])을 비교한다. 이 때 result[1] 은 5 (numbers[3]) 이다.
    • 2 (numbers[0])은 현재 수와 가장 최근의 뒷 수 (numbers[3]) , 가장 최근의 뒷 큰 수 (numbers[3])을 비교한다. 가장 가까우면서 현재 수 보다 큰 수를 찾아야 하므로 results[1] 은 3 (numbers[1]) 이다.
• 예제 2
  • 예제 1과 마찬가지로 numbers 배열의 맨 뒤의 원소 부터 확인한다. result[5] 의 값은 -1이다.
  • 배열을 거꾸로 순회하면서 원소들의 값을 비교한다.
    • 6 (numbers[4]) 은 현재 수와 가장 최근의 뒷 수(= 최근의 뒤 큰수)인 2 (numbers[5]) 와 비교한다. 뒷 큰수가 존재하지 않으므로 result[4] 는 -1 이다.
    • 3 (numbers[3]) 은 현재 수와 다음 수를 비교한다. 다음 수가 현재 수 보다 크므로 result[3] 은 6 (numbers[4])이다.
    • 5 (numbers[2])은 현재 수와 다음 수, 그리고 이전의 수와 비교한다. 다음 수는 현재 수보다 작으므로 넘어가고, 6(numbers[4])이 뒤큰 수가 된다.
    • 1 (numbers[1])은 현재 수와 다음 수, 그리고 이전의 수와 비교한다. 1의 뒤 큰수는 5 이다.
    • 9 (numbers[0] 은 현재 수와 다음 수, 그리고 이전의 수들과 비교한다. 모든 수와 비교했을 때 9보다 큰 수는 없으므로 result[0] 은 -1 이다.

문제의 제약 조건#

4 ≤ numbers의 길이 ≤ 1,000,000

• 1 ≤ numbers[i] ≤ 1,000,000

• numbers 배열의 길이가 1,000,000 이므로 완전 탐색은 불가능하다.
• numbers[i] 는 1,000,000 이하 이므로 int 형 변수로 충분하다.

핵심 문제 파악#

예제를 정리하자면 뒷 큰수를 결정하기 위해서는 현재 수와 바로 옆에 있는 (뒤에 있는 수) 그리고 가장 최근의 뒷 큰 수의 비교가 필요하다. 하지만 가장 최근의 뒷 큰수의 경우, 상대적인 값이다. 즉, 현재 값에 따라 가장 최근의 뒷 큰수가 더 이상 유효하지 않을 수 있다.

예를 들어, [7, 4, 5, 9] 의 경우를 생각해보자.

이 경우 만약 최근의 뒷 큰수와 그 다음 수만 비교하게 된다면 4 (numbers[1] 에 대해서는 results[1] 이 5 가 되고 7 (numbers[0])은 그 다음 수 4 와 최근의 뒷 큰수 5 와 비교하게 되어 -1 로 잘못 판단하게 된다.

이러한 경우를 판단하기 위해서는 현재 값을 기준으로 뒷 큰수가 될 수 있는 값들을 모아두는 것이 필요하며, 뒷 큰수가 될 수 있는 후보는 현재 값보다 크면서 자신보다 뒤에 있는 수 가 될 것이다. 또한 현재 값을 기준으로 그 수보다 크기만 하다면 가장 가까운 값이 뒷 큰수가 되므로 뒤에서 부터 배열을 순회한다고 가정한다면 가장 최근의 값과 우선을 비교해야 할 것이다.

따라서 스택을 통해 뒷 큰수가 될 가능성이 있는 후보들을 담아둔다.

그리고 현재 숫자 numbers[i] 를 기준으로 numbers[i] 보다 작거나 같은 값이 있다면, 그 값들은 numbers[i] 의 뒷 큰수가 될 수 없다. 뿐만 아니라, 앞으로 탐색할 i 보다 왼쪽에 있는 숫자들의 뒷 큰수도 될 수없다. 왜냐하면 numbers[i] 가 앞으로 탐색할 수 보다 더 가깝고, 뒤에 있는 수보다 크기 때문이다.

단조 스택 (Monotic Stack)

이렇게 스택에 원소를 쌓으면서 특정 순서(오름차순 또는 내림차순)을 유지하도록 조작하는 것을 단조 스택(Monotic Stack)이라고 한다.

단조 스택은 스택 내부의 원소들이 항상 단조 증가하거나 단조 감소하는 순서를 유지한다.

스택에 새로운 원소를 추가(push)하기 전에, 스택의 맨 위(top) 원소가 단조 속성을 깨트린다면, 속성이 유지될 때 까지 원소를 제거(pop) 한 후 새로운 원소를 추가한다.

단조 스택을 활용하면 ‘자신보다 크면서 가장 가까운 원소’ 또는 ‘작으면서 가장 가까운 원소’ 등을 자는 문제들을 O(N)의 시간 복잡도로 해결할 수 있다.

시간 복잡도#

배열을 순회하고, 스택에는 최대 배열의 갯수만큼 원소가 들어갔다가 나오므로 시간 복잡도는 O(n) 이다.