문자열 게임

1. 문제 설명

• 문제는 간단합니다. W(지워야 하는) 문자열이 주어지고 그 대상 S 문자열이 주어집니다.
• 그 다음 N 의 숫자가 주어지며 밑으로 N 개의 줄에는 명령어가 주어집니다.

• 명령어 L 은 왼쪽에서 부터 탐색해 처음 등장하는 W 문자열을 제거합니다.
  

• 명령어 R 은 오른쪽에서 부터 탐색해 처음 등장하는 W 문자열을 제거합니다.
  

• 최종적으로 모든 명령을 수행 했을때 문자열 S 에 남은 문자열 W 가 있다면 게임에서 패배하게 됩니다. 출력은 순서대로 성공한 명령어의 수, 남은 문자열 S, 승패 문구 입니다.
  승리한 경우 Perfect!, 패배한 경우 You lose!를 출력합니다. 혼자하는 외로운 게임....
  

2. 접근과 풀이

이 문제는 결론부터 말하자면

입니다.

처음 문제를 접했을 때 이를 무시하고 풀었죠... 아까운 내 90분...

그럼 스택으로 접근해 봅시다!

• aaaaabbbb 라는 문자열 S가 주어지고 ab 라는 문자열 W 가 조건이 되었습니다.
• N = 4
• L L R L

자 조건은 주어졌습니다. 이걸 어떻게 풀어낼까요...?
우선 저는 L 이 주어졌을때 스택을 쌓을 LS list를 R 이 주어졌을때 스택을 쌓을 RS list를 만들었습니다.

• 명령어 L 이 들어왔으니 문자열 S 에서 왼쪽부터 POP하여 LS에 담아줍니다.
  
  첫 문자열 W 가 나왔습니다!!!!!!!!!!!! 네.. 두개 POP 해버립시다. 팝팝팝..!! 팝팝..

• 다음 명령어도 L 이네요..? 다시 PUSH ㄱㄱㄱㄱ
  
  하자마자~ W 등 장 바로 팝팝팝..!! 팝팝.. 해줍시다

• 네.. 이번엔 R 입니다.. RS 에 남은 S 문자열의 오른쪽부터 PUSH 하도록 하죠.
  
  어라... 문자열 S 가 남지 않았어요... 어떡하죠...? 만두 선생님...?

자 생각을 해봅시다.
왼쪽에서 부터 쌓은 LS 오른쪽에서부터 쌓은 RS... 그럼 LS를 POP해서 RS에 PUSH 하면..? 그렇지 문자열이 다시 완성됩니다. 또한 이때부터는 명령어의 종류에 상관없이 명령이 들어오면 그냥 LS를 RS에 쌓으면서 문자열 W 를 뽑아버리면 됩니다.

자 이 상태에서 다시 진행해 보세요.

• 그럼... LS에서 POP 해서... RS로 PUSH...
  
  어! 문자열 W 가 나왔어요! 지워 버려요! 그리고 이걸 반복해요!

• 명령 4번을 다 진행 했더니
  
  이렇게 남았어요.. 저 이긴거죠....?

네 맞아요. 이 경우는 4번의 명령 수행, 남은 문자열 S 는 a 하나 남았고 Perfect! 를 출력해야 합니다.

• 그런데 모든 명령을 수행하고 LS 와 RS 에 모두 문자가 남으면요...?

그럼 합쳐주면 됩니다. LS에 혹은 RS에.. 만약 RS에 담게 된다면 출력시 뒤집어 줘야겠죠?
그리고 합쳤을 때 문자열 W 가 남았을 수 있으니 이 또한 확인해 줍시다.

• 아!.. 그럼 만약 S 에 문자열이 남았을 때도 마찬가지로 LS나 RS로 몰아버리면 되겠네요!

맞아요 그럼 하나의 남은 문자열이 만들어지게 되는거죠. 그럼 이제 코드를 한번 볼까요?

3. 코드

import sys
from collections import deque
input = sys.stdin.readline

W = list(input().rstrip())
S = deque(input().rstrip())
N = int(input())
LS = [] # L 명령시 문자를 담을 스택
RS = [] # R 명령시 문자를 담을 스택
cnt = 0 # 수행한 명령을 담을 변수
for _ in range(N):
    command = input().rstrip()
    if command == 'L':
        while S:
            LS.append(S.popleft())
            # LS의 길이가 W 와 같거나 길고 스택의 윗쪽에 문자열 W가 있을경우!
            if len(LS) >= len(W) and LS[-len(W):] == W:
                cnt += 1 # 수행 + 1
                for _ in range(len(W)): # 그만큼 POP
                    LS.pop()
                break
    elif command == 'R': # 위와 동일합니다.
        while S:
            RS.append(S.pop())
            if len(RS) >= len(W) and RS[-len(W):] == W[::-1]:
                cnt += 1
                for _ in range(len(W)):
                    RS.pop()
                break
    if not S: # 만약 문자열 S 에 문자가 없다면
        while LS: # LS로부터 RS로 뽑아내 주고 
            RS.append(LS.pop())
            # 위와 동일한 동작을 수행합니다.
            if len(RS) >= len(W) and RS[-len(W):] == W[::-1]:
                cnt += 1
                for _ in range(len(W)):
                    RS.pop()
                break
if S: # 모든 수행이 끝났는데 문자열 S에 문자가 남았다면
    while S:
    	# RS로 몰아주고
        RS.append(S.pop())
if LS: # 모든 수행이 끝났는데 문자열 LS에 문자가 남았다면
    while LS:
    	# RS로 몰아주고
        RS.append(LS.pop())

# 출력
ans = "".join(RS[::-1])
print(cnt)
print(ans)
# 문자열 W 가 ans 에 남아있다면!
if "".join(W) in ans:
    print('You Lose!')
# 그게 아닌 모든경우는 
else:
    print('Perfect!')

4. 후기

• 솔찍하게 조금 힘들었습니다. 처음에는 단순히 어라.. 그냥 뽑아내면 안되나 했는데 생각보다 쉽지 않더라구요...
  문자열을 잘 모르겠어요!!!!!! 했더니 나에게 4문제를 주고 그 중 하나는 플레였던....
  내가 풀던 때는 총 54명의 정답자가 있던.... f1rstf1y 고맙습니다..
  이 문제로 자신감을 찾았어요!