dbsrlskfdk   2년 전

처음 알고리즘을 구현했을 떄는, 이중 for문으로 간단하게 체크하면 될 문제라고 생각을 하여 진행했지만 역시나 시간초과를 떴습니다.

그 당시에는 스택을 이용하여 풀이를 생각을 하였지만, 머리로 생각하기엔 이중 for문과 별다를 바 없다 생각하여 좀 사고가 고착화되어 해결하지 못했습니다.

오늘 시간이 지나고 나서 깨끗한 마음으로 스택을 이용한 풀이를 진행하니, 맞았습니다가 떴습니다.

스택을 이용한 알고리즘은 

for문을 통해 입력리스트의 마지막 부터 역으로, 수를 스택에 넣으면서, 비어있지 않다면, top부터 체크하여 자신보다 큰 숫자가 나올떄까지 pop을 하고, 자신보다 큰 수가 나오면, 정답리스트에 넣어두고, 만약 스택이 비어지게 되면 정답이 없는 것이니 -1로 정답을 주었습니다.

마지막에 자신의 숫자는 스택에 다시 넣었습니다. 그리고 반복문을 다시 진행합니다.

맞은 코드라서 코드를 올려도 될지 몰라 일단 말로 서술합니다.

결론은

for(N):

     while(stack size):

이런식으로 반복이 돌아가게 되었는데, 이 과정에서의 최악의 경우는 어떻게 될까요?

만약 입력이 1 2 3 4 5 6 ... 이렇게 주어지게 된다면, stack size 가 계속 1이 되어서 아무 문제 없다고 생각을 했고

9999 9998 9997 9996 ... 이런식으로 주어지더라도 stack size가 계속 1인 상태로 유지되어 괜찮다고 생각했습니다.

이렇게 알고리즘을 구현할 경우, 최악의 케이스는 어떤 것이 될까요?

이런 경우 시간복잡도를 어떻게 생각을 해야하는지 궁금합니다.

ahmg1216   2년 전

다 똑같다 생각됩니다  제 생각엔   O(N) 같습니다

dbsrlskfdk   2년 전

그런게 맞나보군요..

감사합니다!

sait2000   2년 전

넣는 횟수가 O(N)이고 넣은 것보다 많이 꺼낼 수 없으므로 꺼내는 횟수도 O(N)이 됩니다.

dbsrlskfdk   2년 전

역시 그렇군요 감사합니다!

댓글을 작성하려면 로그인해야 합니다.