99클럽 - 뒤에 있는 큰 수 찾기

프로그래머스

아이디어

문제 자체는 이해하기 어렵지 않다.
바로 직관적으로 떠오르는 아이디어를 적용한 코드는 다음과 같다.

def solution(numbers):
    answer = []
    
    while numbers:
        target = numbers.pop(0)
        answer.append(next((val for val in numbers if val > target), -1))
        
    return answer

기본 입출력은 통과했지만  테스트케이스에서는 대다수가 빨간불을 받는다.

• 4 ≤ numbers의 길이 ≤ 1,000,000
• 1 ≤ numbers[i] ≤ 1,000,000

문제는 입력되는 데이터들의 크기인데 100만단위 입출력이면 일반적인 순회법으로는 문제가 생기기 마련이다.
또한 문제 이름 부터가 '뒤에 있는' 이기 때문에 역순으로 판단하는 게 효율적이라는 걸 짐작 할 수 있다.
순서야 그렇다 치고, 이런 경우에는 큐든 스택이든 힙이든 다른 방법을 찾아야 한다는 소리기 때문에 늘 그렇듯 import가 필요한 queue 보다는 stack을 사용했다.

stack은 기본적으로 후입선출 구조로 값의 크기를 비교하는 경우 꽤 유용하게 사용할 수 있다.

풀이

def solution(numbers):
    n = len(numbers)
    answer = [-1] * n
    stack = []

    for idx in range(n - 1, -1, -1):
        while stack and numbers[stack[-1]] <= numbers[idx]:
            stack.pop()
        
        if stack:
            answer[idx] = numbers[stack[-1]]
        
        stack.append(idx)
        
    return answer

데이터의 크기가 크고, 속도에 신경써야 하기 때문에 평소에 가독성을 신경써 사용하던 밸류바인딩이 아닌 인덱스 접근 방식을 사용했다.
입력된 값 만큼의 정답 배열이 필요하기 때문에 필요한 만큼 미리 -1로 초기화하고, 스택에는 인덱스를 저장해 값 복사 횟수를 줄였다.

결과는 최장 528.33ms, 최대 75.5MB로 역시나 오래걸리고 무겁지만 통과에는 문제가 없다.