https://www.acmicpc.net/problem/5002
5002번: 도어맨
첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X<100이 주어진다. 둘째 줄에는 줄을 서 있는 순서가 주어진다. W는 여성, M은 남성을 나타내며, 길이는 최대 100이다. 가장 왼쪽에 있는 글자가 줄
www.acmicpc.net
문제
정인이는 강남의 유명한 클럽 Top Root의 도어맨이다. 클럽의 사장은 정인이에게 클럽이 꽉찼을 때, 클럽에 있는 남자와 여자의 수는 거의 비슷해야 한다고 말해주었다.
사람들은 클럽이 문을 열기 전 부터 줄을 서 있는다. 클럽이 문을 열면, 한 명씩 직접 정인이가 입장시켜 준다. 정인이는 그들이 줄을 순서를 바탕으로 입장시켜 준다. 이때, 항상 첫 번째에 있는 사람을 입장시켜야 하는 것은 아니다. 정인이는 재량을 발휘하여 두 번째로 줄 서있는 사람을 첫 번째 사람보다 먼저 입장을 시켜줄 수 있다. 물론 이런 상황이 자주 발생하면 앞 사람이 매우 짜증이 날 것이고, 정인이에게 시비를 걸 수도 있다. 하지만, 정인이는 모든 싸움을 이길 수 있는 사람이기 때문에 이런 걱정은 하지 않아도 된다.
안타깝게도, 정인이는 이렇게 싸움은 잘하지만, 숫자 계산은 잘 하지 못한다. 정인이는 항상 클럽에 들어가있는 남자와 여자의 차이를 머리속에 계산하고 있어야 한다. 이 차이가 정인이가 기억할 수 있는 값보다 크게 된다면 남은 사람들은 클럽에 입장을 할 수 없게 된다.
줄을 서 있는 순서와 정인이가 기억할 수 있는 차이의 최댓값이 주어졌을 때, 클럽에 있는 사람의 수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X<100이 주어진다. 둘째 줄에는 줄을 서 있는 순서가 주어진다. W는 여성, M은 남성을 나타내며, 길이는 최대 100이다. 가장 왼쪽에 있는 글자가 줄의 가장 앞에 서 있는 사람의 성별이다.
출력
클럽에 있는 사람 수의 최댓값을 출력한다.
사람들이 클럽에 줄을 서 있고, 사람은 남자(M), 여자(W)로 구분한다.
정인이는 클럽에 들어가 있는 남자와 여자의 차이를 계산하고 있어야 하고, 만약 정인이가 기억할 수 있는 숫자보다 크면 남은 사람들은 클럽에 들어갈 수 없다.
예를 들어 남자와 여자의 차이가 2이고 줄을 서 있는 순서가 다음과 같다고 생각해보자.
2
WMMMMWWMMMWWMW정인이는 최대 8명을 입장시킬 수 있다. 남자와 여자의 수를 나타내는 변수 W,M을 선언하고 빈 스택을 하나 만든다.
1) W(여자)를 입장시킴.(스택이 비어있으므로 스택에 W Push)
W++
W = 1, M = 0 (여자 1명,남자 0명) , 클럽에 있는 사람은 총 1명
2)M(남자)를 입장시키고 짝이 맞으니깐 스택을 Pop함
M++
W = 1, M = 1, 절대값 (남자-여자)차이는 0, 클럽에 있는 사람인 총 2명
3)M(남자)를 입장시키고 스택이 비었으니깐 스택에 Push
M++
W = 1,M = 2, 절대값 (남자 - 여자)차이는 1, 클럽에 있는 사람은 총 3명
4)M(남자)를 입장시키고 스택의 Top과 짝이 맞지 않으므로 Push
M++
W = 1,M = 3, 절대값 (남자 - 여자)차이는 2, 클럽에 있는 사람 총 4명
5) 다음 차례가 M인데 M(남자)를 입장시키면
M++,
W = 1,M = 4이므로 절대값(남자 - 여자)의 차이가 3이 되고, 2를 넘어간다.
이때, 정인이의 재량으로 다음 손님과 다다음 손님을 비교해서 다다음 손님을 먼저 입장 시킬 수 있다.
M의 다음은 W이고, 정인이는 이 손님을 먼저 입장시켜야 클럽에 있는 사람이 최대가 되기 떄문에,
다다음 손님을 입장시킨다.
W++,
W = 2, M = 3이므로 절대값(남자 - 여자)의 차이는 1이고, 클럽에 총 5명이 있다.
⭐ i번쨰 i+1번째 줄을 서있는 사람의 성별이 같고, i+1번쨰, i+2번째 줄을 서있는 사람의 성별이 다르면,
i+2번째 사람과 i+1번째 사람의 줄 순서를 바꿔서 스택의 쌍이 맞도록, 최대 길이를 만족하도록 하였다.
ex)
MMW or WWM 일떄i = 1이면 i번쨰는 M(남자) , i+1번쨰는 M(남자) , i+2번째는 W(여자)이다.i와 i+1의 성별이 같고(둘다 남자), i+1번째와 i+2번째 성별이 다르므로(여자) i+1번째, i+2번째 줄 순서를 바꾼다.
-> M W M
WWM도 마찬가지 과정을 거치면
->WMW가 된다.
이런식으로 문제를 해결 할 수 있었다.
#include <iostream>
#include <string>
#include <stack>
#include <cstring>
#include <cmath>
char str[101];
using namespace std;
int main(void){
stack<char> st;
int n;
cin >> n;
cin >> str;
int length = 0;
int W = 0;
int M = 0;
for(int i = 0;i<strlen(str);i++){
//i+1과 i+2의 순서를 바꾼다 (i와 i+1의 성별이 같고 i+1과 i+2의 성별이 다르면)
if(str[i] == str[i+1] && str[i+1] != str[i+2]){
char temp = str[i+2];
str[i+2] = str[i+1];
str[i+1] = temp;
}
}
for(int i = 0;i<strlen(str);i++){
if(abs(M-W) > n){ //클럽에 있는 남자와 여자의 차이의 절대값이 N을 넘어가면
length--;
break;
}
if(st.empty()){ //스택이 비어있는 경우
st.push(str[i]);
length++;
if(str[i] == 'W'){
W++;
}
else if(str[i] == 'M'){
M++;
}
}
else{
if(st.top() == 'M' && str[i] == 'W'){ /*짝이 맞는 경우 */
st.pop();
length++;
if(M != 0){
M--;
}
if(W != 0){
W--;
}
}
else if(st.top() == 'W' && str[i] == 'M'){ /*짝이 맞는 경우 */
st.pop();
length++;
if(M != 0){
M--;
}
if(W != 0){
W--;
}
}
else{ /*짝이 맞지 않는 경우 */
st.push(str[i]);
length++;
if(str[i] == 'W'){
W++;
}
else if(str[i] == 'M'){
M++;
}
}
}
}
cout << length;
}
'알고리즘' 카테고리의 다른 글
| 백준 18114 블랙 프라이데이 C++ (0) | 2022.07.15 |
|---|---|
| 백준 16953 A->B C++ (0) | 2022.07.15 |
| 백준 1599 민식어 C++ (0) | 2022.07.13 |
| 백준 비슷한 단어 2179 C++ (0) | 2022.07.13 |
| 백준 11536 줄 세우기 C++ (0) | 2022.07.11 |