6041 : 최솟값 스택
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
스택에 데이터를 보관하면서, 스택에 현재 존재하는 원소들 중 최솟값(Minimum Value)을 항상 $O(1)$ 시간 복잡도로 꺼내어 볼 수 있는 특수 스택을 만드십시오.
-
-
-
[제약 조건]
• 명령 수 $N$: $1 \le N \le 100{,}000$ (정수)
• push의 인수: $-10^9 \le X \le 10^9$ (정수)
-
push X: 정수 X를 스택에 넣습니다.-
pop: 스택의 가장 위에 있는 원소를 제거합니다.-
min: 스택 내부의 최솟값을 찾아 출력합니다. 비어있으면 -1을 출력합니다.[제약 조건]
• 명령 수 $N$: $1 \le N \le 100{,}000$ (정수)
• push의 인수: $-10^9 \le X \le 10^9$ (정수)
입력 설명
첫째 줄에 명령의 수 $N$이 주어집니다. ($1 \le N \le 100,000$)
둘째 줄부터 $N$개의 줄에 명령이 하나씩 주어집니다.
둘째 줄부터 $N$개의 줄에 명령이 하나씩 주어집니다.
출력 설명
min 명령이 주어질 때마다 현재 최솟값을 각 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
push 5
push 3
min
pop
min
pop
min
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3
5
-1도움
실제 데이터를 담는 일반 스택과, 각 시점의 최솟값을 기록하는 보조 최솟값 스택(min_stack)을 쌍으로 관리합니다. 새로 들어오는 값 $X$가 현재 최솟값 이하인 경우에만 min_stack에 추가합니다.