04/22 알고리즘 공부(98) - 뒤에 있는 큰 수 찾기

조건

정수로 이루어진 배열 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]

알고리즘 예상

1. 간단하게 slice와 first를 이용해서 해결할 수 있을 것 같다.
2. 단 numbers의 길이가 1000000까지 갈 수 있으므로 시간복잡도에 대해서 생각을 해봐야한다.

 

초기 코드

class Solution {
    fun solution(numbers: IntArray): IntArray {
        var answer: IntArray = intArrayOf()
        return answer
    }
}

 

내 코드

// 테스트 케이스 통과, 실패(시간 초과)
class Solution {
    fun solution(numbers: IntArray): IntArray {
        val answer: IntArray = IntArray(numbers.size) { 0 }
        for (i in numbers.indices){
            val number = numbers.slice(i..numbers.lastIndex).filter { it > numbers[i] }
            answer[i] = if (number.isEmpty()) -1 else number[0]
        }
        return answer
    }
}

역시 예상대로 시간초과가 떴다. 다른방법을 이용해봐야겠다.

//성공
import java.util.Stack
class Solution {
    fun solution(numbers: IntArray): IntArray {
        val answer: IntArray = IntArray(numbers.size) { -1 }
        val numbersWithIndex = numbers.mapIndexed { i, c -> i to c }.toTypedArray()
        val stack = Stack<Pair<Int, Int>>()
        for (i in numbersWithIndex) {
            if (stack.isEmpty()) stack.push(i)
            else {
                var peek = stack.peek()
                while (peek.second < i.second) {
                    answer[peek.first] = i.second
                    stack.pop()
                    if (stack.isEmpty()) break
                    peek = stack.peek()
                }
                stack.push(i)
            }
        }

        return answer
    }
}

원래 풀이가 매 원소마다 배열의 끝까지 반복했기 때문에 느렸던 것이라고 생각해 Stack을 이용해 한바퀴만 돌리는 것으로 바꿔보았다.index를 사용할 필요가 있어 map을 이용해 인덱스를 포함해 스택에 넣어주었다.

다른 사람의 풀이

import java.util.*
class Solution {

    fun solution(numbers: IntArray): IntArray {
        val answer = mutableListOf<Int>()
        val s = Stack<Int>()

        for(i in numbers.lastIndex downTo 0) {
            var bigNum = -1
            while(s.isNotEmpty()){
                if(s.peek() > numbers[i]) {
                    bigNum = s.peek()
                    break
                }
                else { s.pop() }
            }
            answer.add(bigNum)
            s.push(numbers[i])
        }
        return answer.reversed().toIntArray()
    }
}

class Solution {
    fun solution(numbers: IntArray): IntArray {
        val n = numbers.size
        val answer = IntArray(n) { 0 }
        answer[n - 1] = -1

        for (i in n - 2 downTo 0) {
            when {
                numbers[i + 1] == numbers[i] -> answer[i] = answer[i + 1]
                numbers[i + 1] > numbers[i] -> answer[i] = i + 1
                else -> {
                    var index = i + 1
                    while (index >= 0 && numbers[index] <= numbers[i])
                        index = answer[index]
                    answer[i] = index
                }
            }
        }

        return answer.map { if (it == -1) -1 else numbers[it] }.toIntArray()
    }
}

개선점 또는 배운점

1. 대부분 스택을 이용해서 풀었다.
2. 아래 풀이는 피보나치 수열문제를 풀 때처럼 DP방식을 이용해 해결했다.