[코딩테스트] 연습문제 - 뒤에 있는 큰 수 찾기

---

문제

 

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

프로그래머스

 

 

numbers 배열을 순회하면서 현재 값 뒤의 수 중에서 현재 값보다 크면서 가장 가까운 값을 담을 배열을 출력하는 문제

 

 

 

---

전략

 

01. 완전탐색

 

 그냥 배열을 순회하면서 뒤에서 본인보다 큰 수가 보이면 그 값을 출력하는 완전탐색

def solution(numbers):
    answer =[]
    for i in range(len(numbers)):
        flag = False
        for j in range(i + 1, len(numbers)):
            if numbers[i] < numbers[j]:
                answer.append(numbers[j])
                flag = True
                break
        if flag == False:
            answer.append(-1)
    
    return answer

 보다시피 이중반복문으로 인해 시간복잡도가 O(n^2)이 된다.

 

 

02. 스택

 가장 가까운 큰 수를 찾아야되므로 현재 값의 다음 값이 현재 값보다 작거나 같은 경우를 생각해보면, 그 다음 값도 탐색해야 한다. 예를 들어 [3, 2, 5]일 경우 3에 들어갈 값은 5가 되어야 한다. 이 때 2는 3보다 원래 작았으므로 이 값 또한 5가 되어야 한다. 즉 [5, 5, 5]이 된다.

 

 따라서 만약 현재 값보다 작은 값들이 있다면 그 값들의 인덱스를 스택에 저장해놨다가 스택의 마지막 값보다 큰 값이 나타나면 스택을 하나씩 빼내서 넣어주면 된다

 

---

풀이

 

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

 

 answer 배열을 numbers의 길이만큼 만들어주는데, 이때 -1로 초기화한다. 만약 마지막까지 순회했는데도 더 큰 값을 못 찾았을 경우 -1을 출력해야 하기 때문이다.

 

 그리고 이제 numbers배열을 순회하는데, while문에서 stack이 존재하고, stack의 마지막 값이 현재 값보다 작다면 현재 값으로 업데이트 해주면 된다.