게임 회사 면접때 받았던질문 하나 더

[익명(106.102)]

스택 자료구조 하나가 있음, 푸시 팝 계속일어나는중

스택에 있는 최솟값을 알고싶음

추가적인 자료구조 써도되는데 어떻게해야 가장 효율적으로 최솟값을 구할수있을까?

- dc official App

[익명(220.94)]

삽입 시 최솟값 갱신될 때마다 스택 x에 푸시하고, 팝 시 그 값이 최솟값이면 x에서도 따라서 팝

[익명(106.102)]

이게 정답임

[익명(222.111)]

스택을 또 만들 필요가 있음? 최소값 변수 하나면 되지 않음?

[익명(106.102)]

최솟값변수하나로 어떻게하게?

[소주(1.225)]

팝시에 스택 x에 있으면 무조건 빼줘아 하는거 아니냐?

[익명(106.102)]

현재 스택의 최솟값이 팝된다면 나머지정보들은?

[펄린이(211.205)]

이거대로 하면 3, 1, 2 들어갔을때 최소값 스택에 3, 1만 들어가는거 아니노? 설명종 해달라 이거야

[익명(220.94)]

뽑을때 2 1 3 순서로 뽑히잖아

[펄린이(211.205)]

아! ㄳㄳ

[익명(104.143)]

너 천재냐

[노이ㄴ(liliilli)]

그냥 변수하나 만들어서 비교하면 안될까 생각하기도 했는데 그건 아닌가보네... 가장 간단하게는 아마 민힙을 만들어서 push, pop 할 때마다 빼주면 되는거. 근데 이 경우에는 push 는 몰라도 pop 할 때 복잡하게 굴러갈 것 같아서 명확한 답은 좀 아닌듯.

[노이ㄴ(liliilli)]

위에 답 맞네 ㅇㅇ

[익명(106.102)]

나도 첨에 민힙같은거 생각했는데 삐빅당함

[익명(106.102)]

결국 트리 이상을 생각하진못했다

[노이ㄴ(liliilli)]

진짜 가장 간단하면서도 빠르고도 명쾌하네 킁

[익명(61.33)]

이런 거 공부할려면 어떻게 해야함? 기초부터 할려는데 책추천좀

[익명(106.102)]

알고리즘도 하고 프로젝트도 해보고 ㅇㅇ