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

문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

---

제한사항

• 4 ≤

  numbers

의 길이 ≤ 1,000,000

• 1 ≤ numbers[i] ≤ 1,000,000

---

입출력 예

numbers	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

---

입출력 예 설명

입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

틀린 제출 답안

• 먼저 max 값을 계속 갱신해나가면서 진행하였다.
• 하지만 이렇게 되면 모든 max가 아닐 경우 계속 2중 for loop를 돌아야 하기 때문에 시간 초과가 발생하였다.

def solution(numbers):
    leng= len(numbers)
    dp = [-1] * leng
    max_val = max(numbers)
    numbers2 = sorted(numbers)
    max_idx = len(numbers2) -1
    for i, val in enumerate(numbers):
        if val == max_val:
            max_idx -= 1
            max_val = numbers2[max_idx]
            continue
        for j in range(i+1, leng):
            if val < numbers[j]:
                dp[i] = numbers[j]
                break
    return dp

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.07ms, 10.3MB)
테스트 5 〉	통과 (0.86ms, 10.4MB)
테스트 6 〉	통과 (12.44ms, 11.4MB)
테스트 7 〉	통과 (16.09ms, 11.5MB)
테스트 8 〉	통과 (78.48ms, 17MB)
테스트 9 〉	통과 (43.60ms, 17.2MB)
테스트 10 〉	통과 (88.38ms, 19.9MB)
테스트 11 〉	통과 (88.65ms, 19.9MB)
테스트 12 〉	통과 (196.56ms, 25.5MB)
테스트 13 〉	통과 (200.19ms, 25.3MB)
테스트 14 〉	통과 (598.74ms, 43.3MB)
테스트 15 〉	통과 (1021.02ms, 75.4MB)
테스트 16 〉	통과 (1139.67ms, 75.5MB)
테스트 17 〉	통과 (1241.03ms, 75.5MB)
테스트 18 〉	통과 (1238.73ms, 75.4MB)
테스트 19 〉	통과 (1201.24ms, 75.4MB)
테스트 20 〉	실패 (시간 초과)
테스트 21 〉	통과 (135.34ms, 72.3MB)
테스트 22 〉	실패 (시간 초과)
테스트 23 〉	통과 (127.71ms, 72.2MB)

찾은 정답 코드

1. stack에 쌓인 인덱스를 기준으로 계속 비교가 가능하다.
2. 이렇게 하면 모든 값을 비교하지 않아도 된다는 장점이 있다.
3. 예를 들어 문제에서 2보다 큰 값을 찾을 때 맨 처음에 stack가 비어 있으니 0번째 인덱스가 stack에 저장된다.
   1. 그 다음에는 3이 오고 stack에 값이 있으니 while문 조건이 충족되면서
   2. numbers[0]값과 현재 3과 비교했을 때 3이 크니 stack에 있던 0 인덱스를 pop하고 answer[0] 을 3으로 업데이트 한다.
4. 이런식으로 계속 비교해 나가면 된다.

def solution(numbers):
    answer = [-1]*(len(numbers))
    stack = []
    for i, val in enumerate(numbers):
        while stack and numbers[stack[-1]] < val:
            answer[stack.pop()] = val
        stack.append(i)
    return answer