[프로그래머스/Swift] Level2 - 뒤에 있는 큰 수 찾기 | PS일지

문제

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

프로그래머스

[ 간단한 문제 요약 ]

정수로 이루어진 배열 numbers 가 있다. 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중 자신보다 크면서 가장 가까이 있는 수를 뒷큰수라고 한다. 뒷 큰수가 존재하지 않을 경우 -1을 담는다. 모든 원소에 대한 뒷 큰수들을 차례로 담아보시오.

 

[ 고려해야 할 사항 ]

• numbers길이 최악의 경우 1,000,000
  • O(n*n)으로 접근시 1억만번의 연산을 해야합니다.

[  1st try:  ) ]

@inline(__always)
func findNextToBigNumber(_ target: Int, numbers: [Int]) -> Int {
  return numbers.first(where: { $0 > target}) ?? -1
}

func solution(_ numbers:[Int]) -> [Int] {
  return numbers.enumerated().map { i, number in
    findNextToBigNumber(number, numbers: Array(numbers[i...numbers.count-1]))
  }
}

 

enumerated()는 O(1) 입니다. 그러나 Array.first(where:)는 O(n) 입니다. 우선 문제를 이해하고자, 빠르게 O(n*n)으로 풀어봤습니다. 시간초과가 발생됬습니다.

 

이 코드의 단점은 매번 자신의 원소보다 큰 원소들을 일일이 찾아야한다는 것이고, 최악의 경우 최대 1,000,000에서 -1씩 계속 탐색된다는 것입니다.

 

동일하게 반복되는 연산이므로, 버퍼를 활용해야했고, 어떻게 활용할지 고민했습니다. 

 

[  2nd try:  ) ]

한가지 떠올린 키워드는 꺼꾸로! 였습니다. 그리고 버퍼에 최근 탐색한 값들을 저장할 때, 가장 가까이에 큰 수를 찾아야 하기에 그리디하게 뒤에서부터 가장 큰 원소는 버퍼에 저장하고, 탐색했던 원소가 버퍼의 특정 원소보다 작으면 추가하는 방식으로 구현했습니다.

 

var buffer: [Int] = []
var res: [Int] = []

func findNextToBigNumber(_ target: Int) {
    var hasFounded = false
    while !hasFounded {
        if buffer.isEmpty { break }
        let element = buffer.removeLast()
        if target < element {
            hasFounded = true
            res.append(element)
            buffer.append(contentsOf: [element, target])
        }
    }
    if !hasFounded {
        buffer.append(target)
        res.append(-1)
    }
}

func solution(_ numbers:[Int]) -> [Int] {
    numbers.reversed().forEach { findNextToBigNumber($0) }
    return res.reversed()
}