자료구조 문제 이거 답이뭘까여

[문제셔틀(112.184)]

<!--StartFragment-->

stack의 push와 pop operation 및 자료구조에서 가장 작은 element

  

를 return 하는 find_min을 지원할 수 있는 자료구조를 제시하라.

  

단, 모든 operation들은 worst time에 O(1). (10점)

<!--[if !supportEmptyParas]--> <!--[endif]-->

find_min을o(1)으로 한다라;;;;

이걸잘모르겟네요..

[장소삼(175.117)]

O1이면 상수로 넣어라는거 아녀?

[장소삼(175.117)]

아니 상수로 넣는게 아니라 constant time

[문제셔틀(112.184)]

이거 생각해봣는데 따로 최소값을 가르키는 포인터두고 push때마다 최소값과 push되는값 비교해서 바꿔주는방식으로하면될거같은데.... 문제는 pop할때네요..만약 최소값이 pop되면 다시 최소값을 계산해야되는데;;결국o(1)만에 최소를 어케찾을수잇을지...B-힙구조를 따로 유지하면그건 좀 문제의도를 벗어난것같고 ㅜㅜ

[20160525(circir6174)]

이거 풀면 답좀 저도 궁금함

[20160525(circir6174)]

스택안에 [자료/이전최소값] 투플을 집어넣는거

[20160525(circir6174)]

어차피 순서대로 빠지니까 pop하다가 이전최소값 필드가 null이 아닌놈이 오면 그 값을 최소값으로 바꺼주고 그러면 될듯

[문제셔틀(112.184)]

네 생각해보니 2016052님말대로 하면 될거같네요 ㅋ