[백준] 1524번 세준세비 - C++ (Stack)

발상

1달 전에 구현으로 낑낑대다가 결국 못 풀고 넘겼던 문제.. 

문득 stack을 이용하면 풀 수 있을 것 같다는 생각이 들어, stack을 이용해 구현해 보았다. 문제의 조건을 보면

가장 약한 병사가 죽는다. 

- 가장 약한 병사가 둘일 때 한쪽에 있다면 둘 중 하나가 죽는다.

- 양쪽에 있다면 세비의 병사가 죽는다.

이 부분이 포인트이다. 우선 주어진 병사들을 내림차순으로 정렬하고, stack에 하나씩 넣은 뒤 top을 비교하면 가장 약한 병사를 찾을 수 있을 것이다. 

 

1. 세준이의 병사가 가장 약하다 (sejuns.top() < sebis.top()) : sejuns.pop(), 즉 세준이의 병사가 죽는다. 

2. 세비의 병사가 가장 약하다. (sejuns.top() > sebis.top()) : sebis.pop(), 즉 세비의 병사가 죽는다. 

이 두 가지 조건에서 가장 약한 병사가 둘일 때 한쪽에 있다면 둘 중 하나가 pop되게 된다. 즉 조건을 구현할 수 있다. 

3. 세준 = 세비라면 세비의 병사가 죽는다. 

이를 구현하면 다음과 같다. 

 

소스코드

#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;

int main (){
	int a;
	cin >> a;
	for(int i=0; i<a; i++){
		int s, b;
		cin >> s >> b;
		
		int sejun[s];
		int sebi[b];
		stack <int> sejuns;
		stack <int> sebis;
		for(int j=0; j<s; j++){
			cin >> sejun[j]; 
		}
		for(int j=0; j<b; j++){
			cin >> sebi[j];
		}
		sort(sejun, sejun+s, greater<int>());
		sort(sebi, sebi+b, greater<int>());
		for(int j=0; j<s; j++){
			sejuns.push(sejun[j]);
		}
		for(int j=0; j<b; j++){
			sebis.push(sebi[j]);
		}
		while (1){
			if (sejuns.top() < sebis.top()) sejuns.pop();
			else if (sejuns.top() >= sebis.top()) sebis.pop();
			
			if(sejuns.empty() || sebis.empty()) break;
		}

		if (!sejuns.empty()) cout << "S\n";
		else if (!sebis.empty()) cout << "B\n";
	}
}

 

우선 case의 개수를 받고, 그만큼 for loop을 돌린다. 

 

그리고 각 case에서의 세준이와 세비의 병사의 수를 받고, 그 크기만큼의 배열을 각각 만든 후, 배열을 내림차순으로 정렬한다. 소스코드는 아래와 같다. 

		int s, b;
		cin >> s >> b;
		
		int sejun[s];
		int sebi[b];
		stack <int> sejuns;
		stack <int> sebis;
		for(int j=0; j<s; j++){
			cin >> sejun[j]; 
		}
		for(int j=0; j<b; j++){
			cin >> sebi[j];
		}
		sort(sejun, sejun+s, greater<int>());
		sort(sebi, sebi+b, greater<int>());

 

정렬해준 배열을 미리 만들어둔 stack에 하나씩 push한다. 이렇게 되면 병사의 힘이 커지는 순서대로 stack에 들어가게 된다. 

		for(int j=0; j<s; j++){
			sejuns.push(sejun[j]);
		}
		for(int j=0; j<b; j++){
			sebis.push(sebi[j]);
		}

 

이제 while(1) 에서 break되는 조건을 둘 중 한 스택이 비었을 때로 설정하고, (어차피 둘 중 한 스택이 비었다면 비지 않은 스택이 이긴 사람의 스택이다.) 스택의 top을 비교하여

-세준 < 세비라면 세준의 병사 pop

-세준 >= 세비라면 세비의 병사 pop 

으로 while문을 작성한다. 

 

		while (1){
			if (sejuns.top() < sebis.top()) sejuns.pop();
			else if (sejuns.top() >= sebis.top()) sebis.pop();
			
			if(sejuns.empty() || sebis.empty()) break;
		}

 

while문이 break되었으므로, 비지 않은 스택을 찾고 답을 출력한다. 

		if (!sejuns.empty()) cout << "S\n";
		else if (!sebis.empty()) cout << "B\n";

 

배운 내용인 stack이라는 자료구조를 사용하여 풀 수 있어 조금은 뿌듯했고 한 달 전에 못 푼 문제다 보니 그래도 한 달 사이에 조금은 늘었구나, 싶었다., ^^ 그래도 오늘은 한 번만에 구현에 성공했다.