5002. [Python]도어맨

1. 문제

 

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

5002번: 도어맨

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 구현
• 큐(queue / 덱)

 

3. 파이썬 코드

 

from collections import deque

N = int(input())

words = deque(map(str,input()))

m_cnt = 0
w_cnt = 0

while words:
    # 리스트 값을 왼쪽부터 뽑으면서
    check = words.popleft()
    # 남자면 m_cnt 1 증가
    if check == "M":
        m_cnt += 1
    # 여자면 w_cnt 1 증가
    elif check == "W":
        w_cnt += 1
    # 만약 두 값의 차가 N 보다 큰 경우
    if max(m_cnt, w_cnt) - min(m_cnt, w_cnt) > N:
        # 리스트가 존재하면
        if words:
            # 값을 한개 더 뽑아본다
            middle_check = words.popleft()
            # m_cnt 값이 w_cnt 값보다 큰 경우
            if m_cnt > w_cnt:
                # m_cnt 값이 위에서 증가됐기 때문에 1 뺀다
                m_cnt -= 1
                # 한개 더 뽑은 값이 W 인 경우
                if middle_check == "W":
                    # w_cnt 값 1 증가
                    w_cnt += 1
                    # M 값이였던 check 값을 리스트에 왼쪽에 더해줌
                    words.appendleft(check)
                # M 인 경우 반복문 종료
                else:
                    break
            # m_cnt 값이 w_cnt 값보다 작은 경우
            elif m_cnt < w_cnt:
                # w_cnt 값 -1
                w_cnt -= 1
                # 한개 더 뽑은 값이 M 인 경우
                if middle_check == "M":
                    # m_cnt 값 1 증가
                    m_cnt += 1
                    # check 값을 리스트에 왼쪽 값에 증가
                    words.appendleft(check)
                else:
                    break
        # 리스트가 없으면
        else:
            # N 값보다 컸을 때 경우이기 때문에
            if m_cnt > w_cnt:
                # 뽑은 값이 M 이였으면 +1 을 해줬기 떄문에 -1
                if check == "M":
                    m_cnt -= 1
            elif m_cnt < w_cnt:
                # 뽑은 값이 W 였으면 +1 을 해줬기 때문에 -1
                if check == "W":
                    w_cnt -= 1
            break
# 반복문이 끝나면 계산한 여자와 남자들이 들어간 갯수 더해줌
print(w_cnt + m_cnt)

 

4. 문제를 풀고난 후 생각

 

• 큐와 구현을 통해서 문제에 조건에 맞도록 구현하는 문제로 여자와 남자의 들어오는 명수를 각자 세어주고 조건에 맞도록 개수를 계산하여 마지막에 총합 값을 나타낸다.
• 리스트의 젤 왼쪽값을 이용해야 하기 때문에 pop(0) 보다는 deque 를 사용하여 시간 복잡도를 줄였고, 여자와 남자의 차가 N보다 큰 경우 에서 리스트에 값이 있는 경우 없는 경우를 체크해서 문제를 풀어줬다.
• 리스트 앞에서 2번째 값까지 확인해야 했고, 이러한 경우의 수를 조건으로 다 처리해줘서 문제를 해결했다.

예를 들어

 

1
WWMMW

라는 값이 올때를 생각해보면

1. 처음 값이 W 나오고 w_cnt 값이 1 증가   => 현재 리스트 : WMMW / w_cnt = 1 / m_cnt = 0

2. 다음 값으로 W 나오고 w_cnt 값이 1 증가 하면 w_cnt - m_cnt 값이 1 을 넘기 때문에 이때 다음 값을 뽑아서 M 인지 W인지 확인해본다. 다음 값이 M 이므로 W 대신 M을 뽑아 w_cnt  -1 해준 후 m_cnt + 1 해주고 W 값을 리스트에 다시 넣어준다.

 

현재 리스트 : WMW  / w_cnt = 1 / m_cnt = 1

 

3. W 값을 뽑아 별다른 조건이 없으므로 w_cnt 값 1 증가 => 현재 리스트 : MW / w_cnt = 2 / m_cnt = 1

4. M 값을 뽑아 m_cnt 값 증가 => 현재 리스트 : W / w_cnt = 2 / m_cnt = 2

5. W 값 뽑아 w_cnt 값 증가 => 현재 리스트 : [] / w_cnt = 3 / m_cnt = 2

 

이렇게 다 뽑고난 후 w_cnt + m_cnt 한 값을 결과로 출력

 

5. 문제를 푸는데 도움이 되는 지식

 

• 큐, 덱