#9935

정현이 형이 풀어보라고 준 문제 중에 마지막!! 당연히 그러면 안되고 그럴 필요가 전혀 없다는 것도 알지만 사실 티어를 보고 나서 살짝 쫄았다.

처음 풀이는 당연히!! 누구나 그랬겠지만 (알고리즘 좀 한다는 고수 분들은 아예 시도조차 하지 않았을 것이다) 문자열 순회하면서 없어질 때까지 지웠다.

inputStr = input()
bombStr = input()
lastStr = ""

while(1):
    if bombStr not in inputStr:
        lastStr = inputStr
        break
    else:
        inputStr = inputStr.replace(bombStr, "")
        # print(inputStr)
if len(lastStr) == 0:
    print("FRULA")
else:
    print(lastStr)

예상은 했지만 60퍼까지 잘 가다가.. 결국 시간 초과

그러고는 문제 분류를 살짝 봤다. 스택!!!
스택 문제를 한번 풀어봤었기에 바로 패드에 끄적이기 시작했다.

진짜 어이가 없을 수 있지만 이게 정석 풀이인 줄 알았다.

모든 문자열을 처음부터 끝까지 순회했기 때문에 시간 초과가 날 수 있겠다라고 생각했고 그 범위를 줄여주면 바로 통과할 수 있겠다고 생각했다 (끄적여본 풀이에는 사실 스택이라고 적어놨지만 스택의 특성(push, pop)은 이용하지 않았고 그냥 문자열 루프 돌린게 맞다..)

입력된 문자열을 돌면서 BombStr(예제 입력에서는 C4)에 포함되어 있는 문자는 따로 저장해뒀다. 이 때 문자열의 원래 위치(인덱스)를 같이 기억한다.

for 루프를 Stack2에서만 다시 돌아서 => 범위가 매우 줄어든다.
C4 문자열을 다 없애주는 작업을 진행한다.

inputStr = input()
bombStr = input()
lastStr = ""

Stack1 = []
Stack2 = []

# i = 0
for i in range(len(inputStr)):
    if inputStr[i] not in bombStr:
        Stack1.append([i, inputStr[i]])
    else:
        Stack2.append([i, inputStr[i]])

print(Stack1)
print(Stack2)
        
# while(1):
for i in range(len(bombStr)):
    for j in range(len(Stack2)):
        if bombStr[i] == Stack2[j][1]:
        ...

하다가 그만 뒀다. 어느 순간에 갑자기? 절대 이게 정답일리 없다고 생각했기 때문이다.

그만두고 나서는 갑자기 이런 생각이 들었다.

분명히 내가 지금 모르는 아주 확실한 키 포인트가 있을거야. 도대체 그게 뭘까? 생각해서 알 수 있는게 아닌가? 그럼 나는 이걸 못푸나?

그 상태로 20분? 30분? 정도 고민을 한 것 같다.

결론.

이러고 있는 시간이 아깝다는 생각이 들기 전에

구글링하자.

inputStr = input()
bombStr = input()
bombLen = len(bombStr)
bombLastChar = bombStr[-1]
Stack = []

for char in inputStr:
    Stack.append(char)		
    # 한 글자씩 스택에 넣는다

    if char == bombLastChar and ''.join(Stack[-bombLen:]) == bombStr:
    # 현재 스택에 넣은 문자가 폭발 문자열의 맨끝 문자와 일치하고,
    # 스택에서 폭발문자열의 길이만큼 문자열을 추출했을 때, 이 문자열이 폭발문자열과 일치한다면?
        del Stack[-bombLen:]			
        # 해당 문자열을 스택에서 제거한다.


if Stack:
    print("".join(Stack))
else:
    print("FRULA")

어떻게 이런 생각을 해낼까

진짜 너무 신기했다.

풀이 방법은 의외로 간단했다. 문자 하나씩 스택에 쌓아 가다가(push) 폭탄 문자열 젤 뒷자리 문자를 보고? 같은 것이 나오면 그 때 그 자리에서 앞으로 폭탄 문자열 길이만큼 비교해보고 맞으면 빼주면(pop) 된다.

아주 정확하게 스택을 이용하여 푸는 문제였다.

문제 풀이에 유용하게 쓰일 문자열 다루는 방법도 몇가지 익혔다.

# 1
''.join(Stack[-bombLen:]) == bombStr:

# 2
del Stack[-bombLen:]			

# 3
print("".join(Stack))

아직까지는 많이 부족하다.

어렵다.

하지만? 이 문제도 "젤 뒤에 문자" 이거 딱 하나에 포커스를 맞췄으면 풀 수도? 있었겠다. 항상 그렇지만 그 "딱 하나의 키 포인트, 핵심"이 떠오르면 끝인데.. 쉽게 풀 수 있는데.. 그게 정말 쉽지가 않다.