99클럽 코테 스터디 1일차 TIL, 프로그래머스 / 뒤에 있는 큰수

🔑 오늘의 학습 키워드 : Stack

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

    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

첫 시도 방식은 Brute force로 시도했다. 

 

그렇게 되면 O(n^2)의 시간 복잡도를 가지게 되는데

 

하지만 제한 조건이 10 ^ 6 이므로 시간초과가 나는것이 당연했다.

이 문제를 풀기 위해서는 계단 문제라고 생각을 했다.

[2,3,3,5] 인 경우

			============
			============
	============	============	============
============	============	============	============
============	============	============	============

이런 식으로 생기게 되는데 자기기준에서 오른쪽을 바라봤을때

처음으로 자기보다 큰 숫자가 자기의 인덱스에 들어가면 되는것이다.

즉, [3,5,5,-1] 인 셈이다. 이해가 가지 않는다면 

다음의 과정을 통해 이해를 해보자.

1. 배열을 순회하면서 자기보다 작은 숫자를 (높이, 인덱스)의 형태로 스택에 담고
2. 스택의 맨위의 값과 비교했을때 큰 숫자면 해당 인덱스에 값을 갱신해주면 되는 것이다.

말이 어려울 수 있는데

스택에는 결국 작은 숫자가 쌓이면서 피라미드 형태가 되는 것이고

거기서 스택 맨위 값이 커질때까지 pop 하며 갱신을 해주면 되는 것이다.

✅ 오늘의 회고

자료구조를 잘 활용해야 하는 문제였다.

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL