골드 4 문제에 도전을 해본다!
당연하게도, 이 문제를 곧이곧대로 반복문 두개로 풀면 시간 초과가 날 것이다.
수열의 크기가 100만까지 커질 수 있지 않는가!
그렇기에, stack을 이용해서 풀었다.
여기서 stack을 구현하는 방식은, 간단하게 말해서 오큰수를 찾지 못하면 stack에 넣고, 오큰수를 찾을 수 있는 경우에서는 stack에서 가능한 만큼 지워주는 방식으로 구현한다.
처음에 -1을 모든 칸에 넣고, stack에 값이 있는지와 없는지로 나누고, stack에 값이 있는 경우에는 stack에서 top이 data의 i번째와 만났을 때 stack이 처리 가능한지로 나눠서 푼다.
어렵다 어려워.!
'Computer Science > Algorithm' 카테고리의 다른 글
| BOJ 6588: 골드바흐의 추측 (0) | 2021.12.25 |
|---|---|
| BOJ 2609: 최대공약수와 최대공배수 (0) | 2021.12.25 |
| BOJ 10799: 쇠막대기 (0) | 2021.12.25 |
| BOJ 9012 괄호 (0) | 2021.12.24 |
| BOJ 10655: 마라톤 1 (0) | 2021.12.21 |