아래 그림은 A 탑과 B 탑 사이에 두 탑보다 작은 탑들이 있는 경우의 그림 입니다.
B 탑 뒤에 있는 탑들은 이 사이에 있는 탑들은 전혀 필요가 없는 탑들 입니다.(비교할 필요가 없습니다) 왜냐하면 B 탑보다 작은 탑들은 B 탑에 걸릴 것이고 , 큰 탑은 A 탑에 걸리거나 아니거나 하겠지요.
B 탑을 처리할 때 이 부분을 없애 버립니다.(스택에서의 pop 개념이지요.) 자기 보다 작은 탑들은 스택에서 pop 해 버리면서 진행 합니다. 자기보다 큰 탑이 나오면 push...
분석
best case에서 O(n)입니다. 2중 반복문으로 구현하는데, 최악의 경우에도 2*n을 동작하지 않습니다.입력이 내림차순 정렬이라면 pop이 일어나지 않습니다. 반대로 오름차순 정렬이라면 각 입력마다 한번씩의 pop이 일어납니다. 이 경우가 worst가 되요. 그러니까 O(n)이죠.
물론 정렬이 안되어잇는 경우라면, pop이 n번이 안됩니다.
시간 복잡도: O(n)