A에 입력을 받고, 맨 오른쪽 원소부터 역순으로 검사하는 방식으로 구현하려고 하였습니다.

변수 설명 : A - 입력 배열, st : 오른쪽으로 진행하며 처음 만나는 큰 수를 찾기 위해 A배열의 역순으로 삽입하기위한 스택, pst : 결과를 출력하기 위한 스택, st[0] : st의 가장 큰 원소로 st[0]보다 큰 원소를 만났을 때 스택을 돌며 시간낭비를 하지 않기 위한 변수

13번째 줄 : A배열의 마지막 원소(역순으로 스택에 넣으므로 반복문의 입장에선 첫번째 원소)의 경우 스택에 넣고, -1을 출력하기 위함

17번째 줄 : 코드 구조상 st배열의 처음에 가장 큰 원소가 들어가게 되는데, 현재까지의 가장 큰 수 보다 더 큰 수가 들어온 경우 -1을 출력하고, 스택을 초기화 하기 위함

21번째 줄 : 가장 오른 쪽 원소를 찾기 위해 스택을 역순으로 돌며 스택에 존재하는 수(j)가 기준 수(i)보다 작다면 스택에서 제거하고, 크다면 오른쪽에 위치하는 첫 번째 큰 수를 찾은것이므로 i를 스택에 넣고, j를 출력하기 위함

예를 들어 설명드리자면 101 4 3 5 100 배열의 경우

1. st에 100이 들어간다, 출력을 위해 pst에 -1이 들어간다 - 13번째 줄

2. 5와 100을 비교한다, 100이 크므로 st에 5를 넣는다, 출력을 위해 pst에 100을 넣는다 (st 상황 : 100, 5)

3. 3과 (100, 5)중 5를 먼저 비교한다, 5가 크므로 st에 3을 넣는다, 출력을 위해 pst에 5를 넣는다(st 상황 : 100, 5, 3)

4. 4와 (100, 5, 3)중 3을 먼저 비교한다, 3이 작으므로 st에서 하나를 pop한다 -> 4와 5를 비교한다, 5가 크므로 st에 4를 넣는다, 출력을 위해 pst에 5를 넣는다 (st 상황 : 100, 5, 4)

5. 101과 st의 최대값인 100을 비교한다, 101이 크므로 st를 101로 초기화한다, 출력을 위해 pst에 -1을 넣는다 (st 상황 : 101) - 17번째 줄

제가 생각했을 때 최악의 경우는 배열이 100 1 2 3 4 5 6 7 8 9 ... 99 101 이런 경우처럼 배열의 양 끝에 큰 수가 존재하는 경우인데 스택을 사용하여 효율적으로 시간을 줄일 방법이 있을까요?? ㅜㅜ