[BOJ]문자열 게임(18241), 문자열

문자열 게임

1. 문제 설명

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

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

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

최종적으로 모든 명령을 수행했을 때 문자열 S에 남은 문자열 W 가 있다면 게임에서 패배하게 됩니다. 출력은 순서대로 성공한 명령어의 수, 남은 문자열 S, 승패 문구입니다.

승리한 경우 Perfect!, 패배한 경우 You lose! 를 출력합니다.

2. 접근과 풀이

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

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

• aaaaabbbb라는 문자열 S가 주어지고 ab라는 문자열 W 가 조건이 되었습니다.
• N = 4
• L L R L
  자 조건은 주어졌습니다. 이걸 어떻게 풀어낼까요...?
  우선 저는 L 이 주어졌을 때 스택을 쌓을 LS list를 R 이 주어졌을때 스택을 쌓을 RS list를 만들었습니다.
  명령어 L 이 들어왔으니 문자열 S에서 왼쪽부터 POP 하여 LS에 담아줍니다.

첫 문자열 W 가 나왔습니다. 2개 POP 해버립시다.
다음 명령어도 L이네요. 다시 PUSH 합니다.

W 바로 pop() 해줍시다
이번엔 R입니다. RS에 남은 S 문자열의 오른쪽부터 PUSH 하도록 하죠.

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

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

그럼... LS에서 POP 해서... RS로 PUSH...

문자열 W 가 나왔습니다. pop() 해줍시다. 그리고 이걸 반복합니다.
명령 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 고맙습니다.