Algorithm / 뒤에 있는 큰 수 찾기

문제

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

1) 문제 풀이

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

결과

2) 코드 개선

⚠️ 문제점 분석

• 이중 for-loop 사용 -> 시간 복잡도 O(N²)
• 모든 i에 대해 j를 순차적으로 끝까지 탐색 -> 비효율적

✅ 개선 포인트

• 스택 자료구조를 활용
• 배열을 역순으로 순회하며 현재 숫자보다 작거나 같은 숫자는 스택에서 제거
• 그 후 스택의 top에 있는 숫자가 "자신보다 큰 수"가 됨
• 없다면 -1

func solution(_ numbers: [Int]) -> [Int] {
    var answer = Array(repeating: -1, count: numbers.count)
    var stack: [Int] = []  // 인덱스를 저장

    for i in stride(from: numbers.count - 1, through: 0, by: -1) {
        let current = numbers[i]

        // 스택에서 현재 값보다 작거나 같은 값 제거
        while let last = stack.last, last <= current {
            stack.removeLast()
        }

        // 스택의 top이 현재 값보다 큰 수이면 정답
        if let last = stack.last {
            answer[i] = last
        }

        // 현재 값을 스택에 추가
        stack.append(current)
    }

    return answer
}

결과