[백준 5002] 도어맨

문제

사람들이 클럽에 입장하기 위해 일렬로 줄 서 있다. 클럽에 입장한 남녀의 차이를 최대 X만큼 둘 수 있다. 기본적으로 줄의 순서대로 사람들을 입장시키지만 남녀의 차이가 X를 넘어가려 한다면 첫 번째 사람대신 두 번째 사람을 먼저 들여보낼 수 있다. 이때 최대 몇 명이 클럽에 입장할 수 있을지 구하라.

 

입력

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

 

출력

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

---

접근

첫 번째 사람과 두 번째 사람의 순서를 바꿔서 입장시킬 수 있다는 것을 스택으로 구현하였다. 먼저 POP한 후에 해당 사람을 입장시키려 할 때 차이가 X를 넘어가려면 다시 스택에서 POP하여 두 번째 사람의 성별을 확인한다. 만약 두 번째 사람을 입장시킬 때 X를 초과하지 않는다면 입장시키고 첫 번째 사람을 다시 스택에 PUSH한다.

 

구현

- 스택을 탐색한다.

- 현재 가장 첫 번째에 있는 사람을 꺼내고 성별을 확인한다.

- 해당 성별에 해당되는 변수에 +1을 했을 때 X 이하라면 입장시키고 성별에 +1한다.

- 하지만 스택에 아직 원소가 존재하고 X를 초과한다면 다음 사람을 POP한다.

- 이때 현재 사람의 성별과 반대일 때를 계산하고 현재 사람을 다시 줄에 세운다.

- 하지만 같은 성별이라면 더 이상 입장할 수 없기 때문에 종료한다.

- 만약 스택에 더 이상 사람이 존재하지 않는다면 다음 사람을 확인하지 않고 바로 종료한다.

while stack:
    cur = stack.pop()
    if cur == 'W':
        if abs((woman+1) - man) <= X:
            woman += 1
        elif stack and abs((woman+1) - man) > X:
            next = stack.pop()
            if next == 'M':
                if abs((man+1) - woman) <= X:
                    man += 1
                    stack.append(cur)
            else:
                break
        else:
            break
    else:
        if abs((man+1) - woman) <= X:
            man += 1
        elif stack and abs((man+1) - woman) > X:
            next = stack.pop()
            if next == 'W':
                if ((woman+1) - man) <= X:
                    woman += 1
                    stack.append(cur)
            else:
                break
        else:
            break

---

전체 코드

import sys
input = sys.stdin.readline

X = int(input())
club_line = input().strip()
stack = []
for p in club_line:
    stack.append(p)

stack = list(reversed(stack))
woman = 0
man = 0

while stack:
    cur = stack.pop()
    if cur == 'W':
        if abs((woman+1) - man) <= X:
            woman += 1
        elif stack and abs((woman+1) - man) > X:
            next = stack.pop()
            if next == 'M':
                if abs((man+1) - woman) <= X:
                    man += 1
                    stack.append(cur)
            else:
                break
        else:
            break
    else:
        if abs((man+1) - woman) <= X:
            man += 1
        elif stack and abs((man+1) - woman) > X:
            next = stack.pop()
            if next == 'W':
                if ((woman+1) - man) <= X:
                    woman += 1
                    stack.append(cur)
            else:
                break
        else:
            break
print(woman + man)