백준5002 도어맨(스택, 그리디 알고리즘)

https://www.acmicpc.net/problem/5002

문제

정인이는 강남의 유명한 클럽 Top Root의 도어맨이다.
클럽의 사장은 정인이에게 클럽이 꽉찼을 때, 클럽에 있는 남자와 여자의 수는 거의 비슷해야 한다고 말해주었다.
사람들은 클럽이 문을 열기 전 부터 줄을 서 있는다.
클럽이 문을 열면, 한 명씩 직접 정인이가 입장시켜 준다.
정인이는 그들이 줄을 순서를 바탕으로 입장시켜 준다.
이때, 항상 첫 번째에 있는 사람을 입장시켜야 하는 것은 아니다.
정인이는 재량을 발휘하여 두 번째로 줄 서있는 사람을 첫 번째 사람보다 먼저 입장을 시켜줄 수 있다.
물론 이런 상황이 자주 발생하면 앞 사람이 매우 짜증이 날 것이고, 정인이에게 시비를 걸 수도 있다.
하지만, 정인이는 모든 싸움을 이길 수 있는 사람이기 때문에 이런 걱정은 하지 않아도 된다.
안타깝게도, 정인이는 이렇게 싸움은 잘하지만, 숫자 계산은 잘 하지 못한다.
정인이는 항상 클럽에 들어가있는 남자와 여자의 차이를 머리속에 계산하고 있어야 한다.
이 차이가 정인이가 기억할 수 있는 값보다 크게 된다면 남은 사람들은 클럽에 입장을 할 수 없게 된다.
줄을 서 있는 순서와 정인이가 기억할 수 있는 차이의 최댓값이 주어졌을 때, 클럽에 있는 사람의 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정인이가 기억할 수 있는 가장 큰 차이 X<100이 주어진다.
둘째 줄에는 줄을 서 있는 순서가 주어진다.
W는 여성, M은 남성을 나타내며, 길이는 최대 100이다.
가장 왼쪽에 있는 글자가 줄의 가장 앞에 서 있는 사람의 성별이다.

출력

클럽에 있는 사람 수의 최댓값을 출력한다.

코드

a=int(input())
b=list(input())
b=list(reversed(b))
mc=0
wc=0
while b:
    c=b.pop()
    if c=="M":
        if abs((mc+1)-wc)<=a:
            mc+=1
        elif b and abs((mc+1)-wc)>a:
            next=b.pop()
            if next=="W":
                if abs((wc+1)-mc)<=a:
                    wc+=1
                    b.append(c)
            else:
                break
        else:
            break
    else:
        if abs((wc+1)-mc)<=a:
            wc+=1
        elif b and abs((wc+1)-mc)>a:
            next=b.pop()
            if next=="M":
                if abs((mc+1)-wc)<=a:
                    mc+=1
                    b.append(c)
            else:
                break
        else:
            break
print(mc+wc)

풀이

a는 정인이가 기억할 수 있는 사람 차이의 수
b는 남자와 여자가 서있는 리스트
pop은 가장 뒤에 있는 원소부터 꺼내는 작업이므로 reverse를 통해 거꾸로 바꿔준다
그리고 mc와 wc는 각각 남자의 수와 여자의 수
먼저 스택에서 POP한 후 해당 사랑을 입장시키려 할 떄 차이가 a를 넘어가면 다시 스택에서 POP하여 두번째 사람의 성별을 확인
만약 두 번째 사람을 입장시킬 때 성별이 반대이며 a를 초과하지 않는다면 입장시키고 첫 번째 사람을 다시 스택에 PUSH
만약 두 번째 사람이 성별이 같다면 더 이상 입장할 수 없기 때문에 종료