뒤에 있는 큰 수 찾기 | 프로그래머스

김태영·2024년 7월 1일

목록 보기

26/33

📍 뒤에 있는 큰 수 찾기

💡 문제

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

⚠️ 제한사항

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

✅ 풀이

👆 첫 번째 풀이 (실패)

문제의 제한사항 자체가 냅다 시간 복잡도를 잘 줄여야한다!라고 나와있지만 우선 냅다 풀어보았다.

numbers의 요소(n)를 인덱스(i)와 함께 하나씩 탐색한다.
- numbers 배열 중 i 부터 마지막 인덱스까지의 요소를 탐색한다.
- 그 중에서 n보다 큰 요소를 찾는다. (이 때, 큰 요소가 여러 개라면 첫 번재 요소를 선택한다.)
- 마지막 인덱스까지 탐색했는데도 없다면 -1을 반환한다.
탐색 후 반환 타입에 맞춰 IntArray로 변환한다.

물론 역시나 결국 시간 초과 엔딩이다.

class Solution {
    fun solution(numbers: IntArray): IntArray {
        return numbers.mapIndexed { i, n ->
            numbers.slice(i..numbers.size-1).firstOrNull { it > n } ?: -1
        }.toIntArray()
    }
}

시간이 많이 소요되는 이유는 너무나 당연하지만 길이가 최대 백만개인 배열을 자르고, 그 자른 배열을 또 탐색해서 그렇다. 모든 요소에 대한 뒷 큰 수가 존재하지 않을 때를 생각해보면 거의 백만개의 배열을 순회하는 것을 백만번 해야되는.. O(n^2)의 시간 복잡도가 나오게 된다.

만약 컴퓨터의 성능이 완전 좋아져서 백만개의 배열을 백만제곱번 돌아도 시간이 얼마 안걸린다면.. 시간 복잡도를 생각하지 않아도 되지 않을까? 그런데 그런 세상에서는 제한사항이 0부터 일억 미만으로 주어지겠지?.. 굿이다. 그냥 공부하는 게 마음 편하다.

✌️ 두 번째 풀이 (성공)

첫 번째 풀이에서는 현재 탐색 중인 숫자의 뒷 큰 수를 구했다면, 이번 풀이에서는 현재 탐색 중인 숫자가 이전 요소들의 뒷 큰수인가를 구하는 방식을 사용했다. 또한 현재 탐색 중인 숫자와 가장 가까운 큰 수를 찾아야하기 때문에 LIFO 구조인 스택을 사용했다.

구한 뒷 큰 수들을 담아둘 numbers의 길이 만큼의 배열을 선언한다.
- -1로 전부 초기화한다.
- 뒷 큰 수를 구한 인덱스만 값을 업데이트 해줄 것이다.
아직 뒷 큰 수를 구하지 못한 인덱스들을 담아둘 빈 스택을 선언한다.
- 가장 나중에 쌓인 인덱스부터 차례대로 뽑아가며 뒷 큰 수를 구하는데 사용할 것이다.
numbers의 요소들을 하나씩 탐색한다.
- 스택에 쌓인 인덱스가 있다면,
- 스택에서 인덱스를 하나씩 뽑아가며 numbers[pop한 인덱스]와 n을 비교한다.
- numbers[pop한 인덱스]가 n보다 작으면 n은 numbers[pop한 인덱스]의 뒷 큰 수이다.
- 따라서 answer[pop한 인덱스]를 구한 뒷 큰 수 n으로 변경해준다.
- 주의할 점은 현재 인덱스를 포함하면 안된다는 것이다.
- 탐색을 마쳤다면, 현재 탐색 중인 요소의 인덱스를 스택에 쌓는다.

import java.util.Stack

class Solution {
    fun solution(numbers: IntArray): IntArray {
        val stack = Stack<Int>()
        val answer = IntArray(numbers.size) {-1}

        numbers.mapIndexed { i, n ->
        	// 스택이 비어있지 않고, n보다 클 때만 반복!
            while (stack.size != 0 && numbers[stack.peek()] < n) {
                answer[stack.pop()] = n
            }
            stack.push(i)
        }

        return answer
    }
}