2026.01.21 스택&큐 문제풀이(백준 9012번, 11866번)

오늘의 문제입니다.

 

본 문제는 기존에 풀었던 괄호 문제에서와 유사한 방식으로, open과 colse의 쌍이 맞는 것을 VPS 그렇지 않은 것은 VPS가 아닌 것으로 취급합니다. VPS라면 YES, 그렇지 않다면 NO를 출력하도록 요구하고 있습니다.

 

문제의 첫줄에는 입력 받을 줄의 수인 N을 입력받아 for문으로 처리.

N번의 줄에 거쳐 입력받는 줄들이 각각 VPS인지의 여부에 따라 if문을 활용해 YES와 NO를 출력하면 되겠습니다.

 

그렇다면 VPS 여부는 어떻게 따지면 될까요?  여기서 사용할 알고리즘은 스택인가요 큐인가요?

기존 괄호 문제에선 open일때 open이 나오면 open의 개수를 증가시키고, close가 나오면 쌍이 맞으므로 open을 지웠던 것 같습니다. 차이는 해당 문제에서는 VPS가 되기 위한 open 또는 close의 최소 개수를 구하는 것이었고 본 문제에서는 VPS여부만 판별하면 되는 더욱 간단한 문제입니다.

또한, 맨 뒤에 생겨날 open, close를 토대로 VPS 여부를 확인하므로 스택이 적절할 듯 싶습니다.

 

그럼 큐를 사용해선 문제를 풀 수 없을까요?

네, 논리적으로 적절하지 않습니다.

왜냐하면 큐는 FIFO구조이므로 이보다는, 가장 먼저 열리는 첫번째 괄호와 맨 마지막 괄호를 비교후 pop 또는 open++를 하는 LIFO구조가 적절합니다.

 

 

풀이는 다음과 같습니다.

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

int main(){
	int N;
	cin>>N;
	
	//N번의 각 줄을 입력 받아 VPS 여부 확인 후 출력
	for(int i=0;i<N;i++){
	
		string stack;
		cin>>stack;
		
		int open=0;
		int close=0;
		
		for(int j=0; j<(int)stack.length(); j++){
			if(stack[j]=='(')
				open++;
				
			else{ 
				if(open>0)   //짝이 있으면 짝을 맞춰주고
					open--;
				else         //짝이 없으면
					close++;
			}
		
		}
		
		string isVps;
		if(open==0 && close==0)   //AND 조건  (OR조건은 ||)
			isVps="YES";
		else
			isVps="NO";
			
		cout<<isVps<<'\n';

	}


	return 0;
}

 

 

 

 

 

 

 

 

 

다음 문제입니다.

K번째 사람을 제거하려면 배열에서 K번째 인덱스의 요소 값을 삭제하면 되겠네요.

N명의 사람이 제거될때까지 삭제를 반복할때 제거되는 순서를 요세푸스 순열이라고 한다면, 요세푸스 순열에 저장된 값은 삭제된 순서대로 누적되겠습니다.

 

 

 

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int N,K;
	cin>>N>>K;
	
	queue<int> queue;
	
	for(int i=1;i<=N;i++){
	//큐에 요소 입력
		queue.push(i);
	}
	
	//배열 만들기
	vector<int> result;
	
	//큐가 빌때까지(N명의 사람이 모두 제거될때까지)
	while(!queue.empty()){
		for(int j=0; j<K-1; j++){    //K번째 사람이 맨 앞에 오도록 
			//맨 앞을 맨 뒤로 이동 
			 queue.push(queue.front()); 
			 queue.pop();    //큐는 맨 앞에서부터 pop
		}
		
		//K번째 사람 제거 
		result.push_back(queue.front()); 
		queue.pop();
	}
	
	cout<<"<";
	for(int k=0; k< (int)result.size(); k++){
		cout<<result[k];
		if(k != (int)result.size()-1)
			cout<<", ";
	}
	cout<<">";
	
	return 0;
}