백준 17298번 오큰수

문제 링크입니다: https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

N의 최대 범위가 백만이기 때문에 O(N^2)으로는 풀 수 없는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 원소 Ai에 대해 오큰수 페어를 지정해 주는 문제이므로 자료구조 스택을 이용했습니다.

2. 수열을 순회하며 다음과 같은 작업을 진행합니다.

2.1 스택이 비어있지 않을 경우 현재 원소와 스택의 top()과 비교합니다.

2.1.1 스택의 top()보다 현재 원소가 클 경우 스택의 top()의 오큰수는 현재 원소입니다.

2.1.2 2.1을 2.1.1의 조건을 만족할 때까지 반복합니다.

2.2 스택에 현재 원소를 넣어줍니다.

3. 수열을 순회했는데도 스택이 비어있지 않을 경우 스택 내 원소들은 오큰수가 없는 것입니다.

 

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~