숫자 배열과 스택이 주어졌을 때, 배열의 모든 요소는 이미 스택 안에 들어 있다고 가정합니다. 이때 목표는 배열의 각 요소를 개별적으로 얻기 위해 필요한 팝(pop) 연산의 횟수를 구하는 것입니다.
스택에는 요소가 내림차순으로 채워져 있습니다. 즉, 첫 번째 요소가 가장 크고, 맨 위(top)에 있는 요소가 가장 작습니다.
예제 1
입력
Stack [ 7,6,2,1 ] array : 2,1,6,7
출력
Count of number of pop operations on stack to get each element of the array are: 3 1 0 0
설명
배열을 0번 인덱스부터 순회합니다. 값 2를 얻으려면 스택을 세 번 팝해야 하므로 arr[0]은 3이 됩니다. 이 과정에서 처음 두 번의 팝으로 7과 6도 함께 꺼내지게 됩니다. 다음으로 값 1을 얻으려면 한 번만 팝하면 되므로 arr[1]은 1입니다. 값 6과 7은 이미 앞서 꺼내졌기 때문에 추가 팝이 필요 없어 arr[2]=arr[3]=0이 됩니다.
예제 2
입력
Stack [ 3,2,1,1 ] array : 1,2,1,3
출력
Count of number of pop operations on stack to get each element of the array are: 3 0 1 0
설명
배열을 0번 인덱스부터 순회합니다. 첫 번째 값 1을 얻으려면 스택을 세 번 팝해야 하므로 arr[0]은 3입니다. 이 과정에서 3과 2도 함께 꺼내집니다. 두 번째 값 2는 이미 꺼내진 상태이므로 팝 횟수는 0입니다. 세 번째 값 1은 아직 꺼내지지 않았으므로 한 번 팝하여 arr[2]는 1이 됩니다. 마지막 값 3 역시 이미 꺼내졌으므로 0입니다.
접근 방식
이 문제는 unordered_map<int, bool> 자료구조를 활용해 특정 요소가 이미 팝되었는지 여부를 확인하는 방식으로 해결할 수 있습니다. 스택에서 요소를 팝할 때마다 해당 값을 맵에 기록하고, 배열 순회 중 이미 기록된 값이 나타나면 팝 횟수를 0으로 처리합니다. 그렇지 않다면 원하는 값을 찾을 때까지 팝을 반복하며 카운트를 증가시킵니다.
- 정수형 배열 arr[]를 준비합니다.
- 요소를 저장할 stack<int> stck를 선언합니다.
- 스택에 요소를 내림차순으로 push합니다.
- 함수 pop_operations(stack<int>& stck, int arr[], int elements)는 배열의 각 요소를 얻기 위한 스택 팝 연산 횟수를 계산해 반환합니다.
- 초기 count 값을 0으로 설정합니다.
- 팝 연산 중 만난 고유한 숫자들을 저장하기 위해 unordered_map<int, bool> um을 사용합니다.
- for 루프를 사용해 배열을 순회합니다.
- temp = arr[i]로 현재 값을 가져옵니다.
- temp가 um에 이미 존재한다면, 팝 연산이 필요 없음을 의미하는 0을 출력합니다.
- 존재하지 않는다면, temp를 찾을 때까지 스택을 팝하면서 각각 팝된 요소를 um에 true로 기록하고 count를 증가시킵니다.
- while 루프가 끝나면 count를 출력합니다.
- 이러한 방식으로 배열의 각 요소에 대한 팝 연산 횟수를 차례대로 출력할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void pop_operations(stack<int>& stck, int arr[], int elements){
int count = 0;
unordered_map<int, bool> um;
cout<<"Count of number of pop operations on stack to get each element of the array are: ";
for (int i = 0; i < elements; ++i){
int temp = arr[i];
if (um.find(temp) != um.end())
{ cout << "0 "; }
else{
count = 0;
while (stck.top() != temp){
um[stck.top()] = true;
stck.pop();
count++;
}
stck.pop();
count++;
cout<<count<<" ";
}
}
}
int main(){
int elements = 4;
int arr[] = { 2, 1, 6, 7};
stack<int> stck;
stck.push(1);
stck.push(2);
stck.push(6);
stck.push(7);
pop_operations(stck, arr, elements);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of number of pop operations on stack to get each element of the array are: 3 1 0 0