2026.01.22 스택&큐 (백준 1966번, 4949번)

안녕하세요. 벌써 방학의 절반 이상이 지나가고 있네요.

오늘도 역시 문제 2문항 풀어보겠습니다. 

 

 

 

프린터가 FIFO방식으로 프린팅한다고 이야기하고 있습니다. FIFO면 큐 알고리즘을 사용해야겠네요.

그러나 새로 만든 프로그램에 의하면 큐의 front가 다른 요소들보다 중요도가 가장 큰 경우에만 인쇄를 하고, 그렇지 않을 경우 맨 뒤로 보내야 한다고 합니다. 큐의 front보다 다른 요소의 중요도가 더 클 경우 큐의 front를 push해서 맨 뒤에 삽입하고 front는 pop을 해주면 되겠습니다. 

 

입력의 첫줄에는 테스트 케이스의 개수를 입력받습니다.

각 테스트 케이스는 총 두 줄에 거쳐 입력되는데 첫번째 줄에는 N과 M이 주어집니다. 이때 N은 문서의 개수, M은 M번째 인덱스가 정렬 후 몇번째 순서로 출력되는지 순서를 구하며 이때 인덱스 0-based indexing를 기반으로 합니다.

테스트 케이스의 두번째 줄은 각 문서의 중요도를 나타냅니다.

 

 

 

문서들을 큐에 (중요도,초기 인덱스) pair로 넣어주고, 최대힙을 하나 더 만들어 중요도를 넣어주려 합니다.

코드는 다음과 같습니다.

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

int main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin>>t;
	
	//테스트 케이스만큼 반복하기
	while(t--){
		int N,M;
		cin>>N>>M;
		
		//초기 인덱스와 중요도
		queue<pair<int,int>> queue;
		//우선순위 큐
		priority_queue<int> pq;
		
		for(int j=0;j<N;j++){
			int number;
			cin>>number;
			
			queue.push({number, j});   //중요도와 인덱스 
			pq.push(number);
		}
		
		
	int count=0; 
	
	while(!queue.empty()){
		auto front=queue.front();   //auto: 변수타입 자동 추론
		queue.pop();
		
		if(front.first==pq.top()){
			pq.pop();
			count++;
			
			if(front.second==M){
				cout<<count<<'\n';
				break;
			}
		}
		else{
			queue.push(front);
		}
	}
	
}	
	return 0;
}

 

 

 

 

코드를 제출해도 오류가 몇번 나서 확인을 해보니, 제가 변수명을 int try로 만드는 바람에 컴파일러가 예외처리 키워드로 받아들였던 것이었습니다. 따라서 int t로 다시 바꿔 문제를 풀었습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

두번째 문제입니다.

지난번 풀었던 문제처럼 N개의 정해진 입력을 받는 것이 아닌, 원하는만큼 입력 후 입력을 종료하고 싶을때 온점 "."를 입력하면 된다고 하니 while문을 사용하고 break 조건을 주면 되겠습니다.

각 줄은 알파벳과 소괄호, 대괄호, 온점, 공백으로 이루어진다고 합니다.

pair가 맞아야하는 소괄호, 대괄호와 종료조건인 온점에만 유의하면 되겠습니다.

 

또한 여기서는 짝이 맞는지 괄호를 확인해야하므로 LIFO인 스택을 사용하면 되겠습니다.

 

 

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

int main(){
	
	while(true){
			string story;
			//한 줄 전체 입력 받기(공백 포함)
			getline(cin, story);
			
		if(story==".") break;


		stack<char> stack;
		bool isBalance=true;
		
		for(int i=0; i<(int)story.size(); i++){
			char a=story[i];
			
			//open
			if(a=='(' || a=='[') stack.push(a);
			
			//close
			else if(a==')'){
				if (stack.empty() || stack.top() !='('){
					isBalance=false;
					break;
				}
				stack.pop();
			}
			
			//close2
			else if(a==']'){
				if(stack.empty() || stack.top()!='['){
					isBalance=false;
					break;
				}
				stack.pop();
			}	
	}
		
	if(!stack.empty())
		isBalance=false;
	if(isBalance)
		cout<<"yes"<<'\n';
	else
		cout<<"no"<<'\n';
	
	
	}

	return 0;
}

 

 

적절한 if-else if-else의 사용과 언제 isBalance가 false가 될 수 있는지 생각해내는게 문제풀이의 핵심이라고 할 수 있겠습니다.