[Algorithm] 프로그래머스 - 뒤에 있는 큰 수 찾기 (Swift)

문제 소개

프로그래머스

숫자의 배열이 주어지면 자신보다 뒤에 있는 숫자 중에 자신보다 크면서 가장 가까이 있는 수로 바꾸고 없다면 -1로 바꾸는 문제이다. 예를 들면 [2, 3, 3, 5]가 주어지면 [3, 5, 5, -1]을 출력해야 한다.

문제 풀이

뒤에 있는 숫자 중 자신보다 크면서 가장 가까이 있는 수라는 점에서 뒤에서 접근해야 한다는 힌트를 얻었다. 자기와 가장 가까워야 한다는 조건이 있어 정렬은 의미가 없다.

 

뒤에서부터 접근하면서 가장 마지막 값과 비교가 필요하다는 점에서 stack구조를 떠올렸다. 아이디어는 만약 현재의 값이 stack의 맨 마지막 값보다 크다면 stack의 맨 마지막 값까지 가기전에 현재의 값이 앞에서 채택될 것이다. 만약 stack의 맨 마지막 값이 현재의 값보다 크다면 그것이 제일 가깝고 큰 값이므로 answer에 넣어주고, stack의 맨 마지막 값이 그 다음 비교할 값보다 가장 가까우면서 큰 것을 보장할 수 없으므로 현재의 값을 stack의 맨 마지막에 넣어준다. 만약 stack이 비어있다면 현재의 값을 넣어주고 answer에는 -1을 유지해주면 된다. stack 데이터 구조를 활용한 DP...? 정도로 생각하면 될 것 같다.

func solution(_ numbers:[Int]) -> [Int] {
    var answer = Array(repeating: -1, count: numbers.count)
    var stack = [Int]()
        
    for i in (0..<numbers.count).reversed() {
        while !stack.isEmpty {
            let cnt = stack.count
            if stack.last! > numbers[i] {
                answer[i] = stack.last!
                stack.append(numbers[i])
                break
            } else {
                stack.removeLast()
            }
        }
        if stack.isEmpty {
            stack.append(numbers[i])
        }
    }
    return answer
}

 

시간복잡도?

아래와 같이 이중 for문으로 작성을 해보았다. 내 뒤에 있는 숫자 중 나보다 큰 수를 발견하면 바로 break 하고 정답에 반영한다.

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var answer = Array(repeating: -1, count: numbers.count)
    
    for i in numbers.indices {
        for j in 0..<numbers.count-i {
            if numbers[i+j] > numbers[i] {
                answer[i] = numbers[i+j]
                break
            }
        }
    }
    return answer
}

 

하지만 역시... 입력받는 numbers의 길이가 최대 100만이었기 때문에 시간초과가 발생하였다. 그렇다면 내가 낸 통과된 답변이랑 비교해 보면 신기하게 18번, 19번의 경우는 오히려 1.8배 정도 빠른 것을 볼 수 있었다. 0.68초 1.26초면 그래도 유의미한 차이라고 생각한다. 아마 테스트 20번 ~ 23번의 경우는 [1, 1, 1, 1, 1 ..... 100]처럼 준 듯 싶다.

이중 for문의 실행결과 (왼쪽) 통과한 답안 실행결과 (오른쪽)

 

그렇게 된다면 의문이 생겼다. 둘의 시간복잡도는 차이가 있을까? stack을 활용한 풀이의 시간복잡도에 대해서 질문하기 게시판에도 물음이 많은데, 시간복잡도에 대해서 많은 고민을 했다...

 

2024년의 미숙한(?) 내가 낸 결론은 시간복잡도는 O(N^2)으로 동일하나 알고리즘의 힘으로 많은 데이터도 실제로 O(N^2)보다는 짧은 시간이 적용 되는것 같다... NlogN이라는 사람도 있고, 그냥 N이라고 하는 분도 있는데 정말 최악의 경우 while문에 stack이 N개 쌓여있고, 그것을 모두 순회해야 하니까 for문의 N번에 N회 순회... N^2가 아닐까... 조심스럽게 추측해본다. 나중에 꼭 이 문제를 다시 보면서 시간복잡도에 대해서 고민해 봐야겠다.