[Algorithm] 뒤에 있는 큰 수 찾기

[hwangJi-dev]

💬 문제

[코딩테스트 연습 - 뒤에 있는 큰 수 찾기](https://school.programmers.co.kr/learn/courses/30/lessons/154539)

💬 Idea

첫번째 아이디어

기준 인덱스 + 1 부터 끝까지 완전탐색을 하여 기준 인덱스보다 큰 수를 발견하면 answer에 append하고 break하여 이중 포문을 탈출하자.

→ 하지만, 시간초과가 발생했다.

두번째 아이디어

stack을 사용하여 저장하고 stack의 마지막 원소를 pop해가면서 기준 인덱스와 비교하자.

→ 인덱스를 같이 저장하기 위해 stack을 튜플 형태로 저장할 수 있도록 하였다.

💬 풀이

실패한 풀이 - 완전탐색 진행

→ 테스트케이스 20, 21, 22, 23 시간초과 발생

import Foundation

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

성공한 풀이 - stack 사용

import Foundation

func solution2(numbers:[Int]) -> [Int] {
    var ans = Array(repeating: -1, count: numbers.count)
    var stack: [(Int, Int)] = [(0, numbers[0])] // 인덱스를 같이 저장하기 위해 튜플 형태로 저장
    
    for i in 1..<numbers.count {
        // stack이 비어있지 않을때까지 반복
        while !stack.isEmpty {
					  // stack의 마지막 value가 기준값보다 크다면 break 
            if stack.last!.1 >= numbers[i] { break }
            // stack의 마지막원소를 지우고 해당 인덱스에 큰 수 할당
            ans[stack.removeLast().0] = numbers[i]
        }
        // stack에 현재 기준값 저장
        stack.append((i, numbers[i]))
    }
    
    return ans
}