2026.01.21 스택&큐 문제풀이(백준 15828번, 10799번)

 

오늘의 문제는 백준 15828번, 10799번 입니다.

 

 

 

 

 

라우터에서는 버퍼를 FIFO로 처리 후 제거하므로 버퍼는 큐 알고리즘을 따른다고 볼 수 있습니다.

첫줄에는 버퍼의 크기인 N이, 이후에는 라우터가 처리할 정보들이며 양수는 패킷의 번호, 0은 패킷을 처리했다는 의미이며 -1은 입력 종료라고 합니다.

 

그렇다면 큐를 생성해 양수일 경우 수를 순서대로 큐에 넣어주고, 0일 경우 가장 앞의 요소를 pop, -1라면 종료후 큐에 남은 요소들을 출력하면 되겠습니다.

단, N에 유의하여 큐가 N 이상 저장할 수 없도록 해야 합니다.

if-else문을 바쁘게 사용해주면 되겠네요.

 

 

 

#include<iostream>
#include<queue>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N;
	cin>>N;
	
	queue<int> queue;
	
	while(true){
		int order;
		cin>>order;
		
		if(order==-1) break;  //반복실행 루프 생성 후 종료 조건을 추가하기
		
		if(order>0){
			if((int)queue.size()<N){  //저장공간 N 지키기
				queue.push(order);
				}
			}else if(order==0){
				if(!queue.empty())   //큐가 비어있지 않다면 제대로 pop 
					queue.pop();
	  }			
	
	
	}
	
	if(queue.empty()){
		cout<<"empty\n";
	} else{
			while(!queue.empty()){
				cout<<queue.front()<<" ";
				queue.pop();
			 }
	  cout<<'\n';
	}
	
	return 0;
}

 

문제를 풀며 고민한 부분은 -1입니다.

보통 첫줄 입력 N이 입력할 줄의 수였기에 for문으로 처리해주면 쉬웠는데요, 이 문제에서는 -1이 되기 전까지 입력을 계속 받아야 했기에 고민이 조금 생겼던 것 같습니다.

고안한 방법은 조건 없는 while문을 만들어 -1일때 종료하도록 종료조건을 만들어주는 것이었습니다.

 

 

 

 

 

 

 

 

 

 

 

다음 문제는 쇠막대기 문제입니다.

 

문제는 이해가 가지만 어떻게 풀어야할지 조금은 고민이 되는 문제인 것 같습니다.

()는 레이저, (       )는 쇠막대기일때 레이저로 잘라진 쇠막대기 조각의 개수를 구해야 합니다.

가장 최근에 열린 막대기가 가장 먼저 닫히믈 LIFO구조로 스택을 활용해 풀 수 있습니다.

 

 

 

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

		string st;
		cin>>st;
		
		stack<char> stack;
		int count=0;
		
		for(int i=0;i< (int)st.size(); i++){
			if(st[i] == '('){
				stack.push('(');
				}
			else{
				stack.pop();
				if(st[i-1]=='('){
					count+=stack.size();
				}
				else
					count+=1;
			}
			
		}
		
		cout<<count<<'\n';
				
		return 0;	
		
}

 

코드는 다음과 같이 나타낼 수 있습니다.