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

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

프로그래머스

 

접근

---

• 뒤에 있는 숫자들 중에서 자신보다 크면서 가까이에 있는 수를 찾기
  • 뒤에서부터 점검하면서 원소의 추가와 삭제가 빠르게 이뤄져야 한다 
    ➡️ 스택 활용

 

로직

---

• numbers의 마지막 원소는 뒤에 원소가 존재하지 않기 때문에, 반드시 -1을 반환해야 한다. 따라서 answer에는 -1을 포함하여 초기화하고, stack에는 마지막 원소 값을 넣어서 초기화한다. 
• number의 크기 - 2 인덱스부터 인덱스 0까지 -1을 감소시키며 반복문을 수행한다. 
• 인덱스에 대한 반복문을 돌면서, stack에 값이 존재할 때까지 while문을 통해 최댓값을 찾는다
• 만약 stack의 크기가 0이라면, 현재 점검 중인 원소보다 큰 값이 존재하지 않기에 answer에 -1을 담는다. 크기가 0이 아니라면, stack의 맨 위에 있는 원소(마지막 원소)를 담는다
• stack에 현재 가리키고 있는 number를 넣어주며 반복문의 한 차례를 종료한다

 

가장 가까운 최댓값을 찾는 과정

• 원소 5를 점검하고 있다고 했을 때, 바로 직전에 원소 3에 대한 점검을 끝내고 원소 3이 stack에 새롭게 추가된 상황이다
• 새로 추가된 원소 3보다 현재 점검 중인 원소가 크다면, 원소 3을 점검했을 당시 원소 3보다 작은 것은 모두 제거되고, 가장 가까운 6이 남은 것이므로, 원소 5 또한 5보다 크면서 가장 가까운 원소는 6이 된다. 

 

코드

---

1. Swift 풀이 1

• ans에 원소를 하나씩 추가한 이후, 마지막에 reverse 시킨 후 반환한다.
• 인덱스 0에 insert 시키는 로직을 작성할 경우, 포인트를 맨 앞으로 이동시키는 과정을 거쳐야 하므로 많은 시간이 소요된다

func solution(_ numbers:[Int]) -> [Int] {
    
    var ans = [-1]   
    var stack = [numbers.last!]
    for i in stride(from: numbers.count-2, to: -1, by: -1) {
        
        while !stack.isEmpty && stack.last! <= numbers[i] {
            stack.removeLast()
        }
        
        if stack.isEmpty {
            ans.append(-1)
        }
        else {
            ans.append(stack.last!)
        }
        
        stack.append(numbers[i])
    }
    
    return ans.reversed()
}

 

2. Swift 풀이 2

• 원소를 하나씩 추가하는 것이 아닌, 인덱스로 접근해 필요할 경우에만 값을 갱신한다

func solution(_ numbers:[Int]) -> [Int] {
    
    var ans = [Int](repeating: -1, count: numbers.count)
    var stack = [numbers.last!]
    for i in stride(from: numbers.count-2, to: -1, by: -1) {
        
        while !stack.isEmpty && stack.last! <= numbers[i] {
            stack.removeLast()
        }
        
        if !stack.isEmpty {
            ans[i] = stack.last!
        }

        stack.append(numbers[i])
    }
    
    return ans
}

 

3. Python 풀이

def solution(numbers):
    
    answer = [-1] * len(numbers)
    stack = [numbers[-1]]
    
    for i in range(len(numbers)-2, -1, -1):
        
        while len(stack) > 0 and stack[-1] <= numbers[i]:
            del stack[-1]
        
        if len(stack) != 0:
            answer[i] = stack[-1]
        
        stack.append(numbers[i])
    
    return answer