🔑 오늘의 학습 키워드 : 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
'Coding test' 카테고리의 다른 글
99클럽 코테 스터디 3일차 TIL, 프로그래머스/숫자 문자열과 영단어 (2) | 2024.07.24 |
---|---|
99클럽 코테 스터디 2일차 TIL, 프로그래머스/숫자 카드 나누기도움말 (2) | 2024.07.23 |
[백준/14499/파이썬] 주사위 굴리기 - 구현 (0) | 2024.04.09 |
sort(), sorted() 실행 시간 in 백준 (0) | 2024.03.19 |
[프로그래머스/파이썬/가장 큰 정사각형 구하기] (0) | 2024.03.09 |