[Algorithm] 2주차 스터디 - 스택_큐_덱(백준 10828, 10799, 2346, 3078)

A - 10828 스택(S4)

https://www.acmicpc.net/problem/10828

10828번: 스택

 

문제 풀이

 

정수를 저장하는 스택에 대하여 각 기능을 구현한다. 문제에서 요구하는 기능들이 이미 stack 라이브러리에 구현된 기능이므로, 각 입력에 맞게 해당되는 내용을 출력한다.

 

코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    // 개수
    int n;
    cin>>n;

    stack<int> stack; 
    
    // 명령어별 기능
    for(int i=0; i<n; i++) {
        string str; 
        cin >> str;

        if (str == "push") { 
            int n;
            cin >> n;
            stack.push(n);
 
        } 
        else if (str == "pop") { 
 
            if (stack.empty()) {
                cout <<-1<<endl;
            } 
            else {
                cout << stack.top() << endl;
                stack.pop();
            }
        } 
        else if (str == "size") {
            cout << stack.size() << endl;
        } 
        else if (str == "empty") {
            if (stack.empty()) {
                cout << "1" << endl;
            } 
            else {
                cout << "0" << endl;
            }
        } 
        else if (str == "top") {
            if (stack.empty()) {
                cout << "-1" << endl;
            } 
            else {
                cout << stack.top() << endl;
            }
 
        }
 
    }
    return 0;

}

 

 

B - 10799 쇠막대기(S3)

https://www.acmicpc.net/problem/10799

10828번: 스택

 

문제 풀이

 

문제가 길지만 천천히 잘 읽어보면 결국에는 괄호 계산식을 사용하는 스택과 동일하다. 여는 괄호 "("가 나왔을 경우 스택에 push하고, 닫는 괄호 ")"가 나왔는데 그 바로 이전에 여는 괄호가 있다면 레이저가 있는 것이므로 현재 스택의 사이즈(즉, 막대기의 차수)를 전체 값에 더한다. 그렇지 않을 경우 막대기의 차수가 늘어난 것임을 확인할 수 있어 전체에 1을 더해주고 스택 안의 값을 pop 해준다.

전 과정을 다 하면 전체 값을 출력한다.

 

코드

#include <iostream>
#include <stack>
#include <string>

using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

	stack<char> stack;
	int total(0);

	// 개수
    string str;
	cin >> str;

	for (int i(0); i<str.length(); i++) {
		if (str[i] == '(') {
			stack.push(str[i]);
		}
		// 레이저
		else if(str[i]==')' && str[i-1]=='('){
			stack.pop();
			total += stack.size();
		}
		else {
			total++;
			stack.pop();
		}
	}
	cout<<total<< endl;
    return 0;

}

 

C - 2346 풍선 터트리기(S3)

https://www.acmicpc.net/problem/2346

10828번: 스택

 

문제 풀이

 

풍선의 방향 구현을 고민하다가 덱을 활용하여 문제를 풀었다. 풍선을 터트리고 그 수만큼 이동하고 이동하는 과정에서의 풍선은 다시 push하는데 그 수가 음수일 경우 뒤에서 꺼내서 앞에 넣고, 양수일 경우 앞에서 꺼내서 뒤에 넣었다. 이동한 해당 풍선은 pop 하고 출력한다. 

 

코드

#include <iostream>
#include <stack>
#include <vector>
#include <string>

using namespace std;

typedef pair<int, int> pairs;
deque<pairs> balloon_deque;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    // 개수
    int n, argument;
    cin>>n;
	
    // 풍선
    for (int i(0) ; i<n ; i++) {
        cin>>argument;
        balloon_deque.emplace_back(i+1, argument);
    }

    while (!balloon_deque.empty()) {
        pairs balloon=balloon_deque.front();
        cout<<balloon.first<<' ';
        balloon_deque.pop_front();

        // 해당 수 전까지의 다시 push
        // 타겟 풍선은 pop
        for (int i(1) ; i<balloon.second ; i++) {
            balloon_deque.push_back(balloon_deque.front());
            balloon_deque.pop_front();
        }
        
        for (int i(0) ; i>balloon.second ; i--) {
            balloon_deque.push_front(balloon_deque.back());
            balloon_deque.pop_back();
        }
    }

    return 0;

}

 

D - 3078 좋은 친구(G3)

https://www.acmicpc.net/problem/3078

10828번: 스택

 

문제 풀이

 

이미 성적 순으로 배열된 상태이기 때문에 큐를 사용하였다. 숫자를 입력 받으면 앞에서부터 해당 등수까지의 값을 순차적으로 pop 해주고 큐에 남아있는 개수 만큼을 총합에 넣어준다. 이름의 길이를 저장시켜줘서 자신과 이름의 길이가 같은 친구들이 있는 큐를 사용하는데, pop 되지 않았으면 등수 차이가 유의미한 것이므로 큐에 남아있는 친구의 수가 나와 친구가 될 수 있다는 점을 이용한다.

 

코드

#include <iostream>
#include <stack>
#include <queue>
#include <string>

using namespace std;

string Student[300010];

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // 게수
    int n, k;
    cin>> n>>k;

    // 사람
    for (int i(1); i<=n ;i++) {
        cin>> Student[i];
    }

    long long pair_num = 0;
    queue<int> friend_queue[25];

    for (int i(1) ; i<=n ; i++)
    {
        int len = Student[i].length();
        while (i-friend_queue[len].front() > k && friend_queue[len].empty()==false){
            friend_queue[len].pop();
        }
        pair_num+=friend_queue[len].size();
        friend_queue[len].push(i);
    }
    cout<<pair_num<<"\n";

    return 0;
}