[Python][BOJ 백준][Silver II] 1406. 에디터, [Gold IV] 9935. 문자열 폭발 : 스택 아이디어 떠올리기

접근 방식

처음엔 커서를 하나의 문자열로 두고 편집기 명령어에 따라 이동시키려 했다.

알고리즘 분류가 스택인걸 먼저 확인하고 문제를 접했는데, 커서를 이동시키는 방식을 스택에 대입시키기가 쉽지 않아서 많은 고민을 했는데, 두개의 스택을 사용하면 된다는 아이디어를 접했다. 스택 유형의 문제를 많이 풀어보지 않은 나에겐 꽤나 센세이션 했다

 

1. 두개의 스택을 만든다. 이를 왼쪽 스택과 오른쪽 스택이라고 가정했다.
2. 두 스택 사이에 커서가 있다고 생각하자. 커서는 고정이 커서 대신 스택의 요소들이 움직인다.
3. 커서는 초기에 문장의 맨 뒤에 위치하고 있다고 했으므로 왼쪽 스택에는 초기 문자열(입력값) 모두를 넣어두고, 오른쪽 스택은 비워둔다.

예제 입력 2 예시

✅ Solution 1

import sys
stack_l = list(sys.stdin.readline().rstrip())
stack_r = []
m = int(sys.stdin.readline())

for _ in range(m):
    n = sys.stdin.readline().rstrip().split()
    if n[0] == 'L':
        # 커서 왼쪽으로 옮기기 -> stack_l에서 stack_r로 pop
        if stack_l: # 비어있지 않다면
            stack_r.append(stack_l.pop())
        # else일 때 continue안해도 되겠지?
    elif n[0] == 'D':
        # 커서 오른쪽으로 옮기기 -> stack_r에서 stack_l로 pop
        if stack_r:
            stack_l.append(stack_r.pop())
    elif n[0] == 'B':
        # 커서 왼쪽 문자 삭제 -> stack_l에서 pop
        if stack_l:
            stack_l.pop()
    elif n[0] == 'P':
        # n[1]을 커서 왼쪽에 추가 -> stack_l에 append
        stack_l.append(n[1])

stack_r.reverse()
stack = stack_l + stack_r
print(*stack, sep='')

아이디어를 떠올리는게 힘들지, 구현은 단순하다.

 

이 코드 내에서는 stack_r.append(stack_l.pop())가 그나마 주목할만한 부분인 것 같다.

append()의 parameter로 pop()을 바로 넣어서 pop()의 반환값을 바로 append할 수 있다.

 

그리고 stack_r을 출력할 때 반대로 뒤집어줘야 한다.

접근 방식에 첨부한 그림상에서 stack_r에 c, b, a, x 순으로 append하므로 stack_r = [c, b, a, x] 인데, 출력할 때는 x, a, b, c 순으로 출력해야 하기 때문이다.

✅ Solution 2

import sys
stack_l = list(sys.stdin.readline().rstrip())
stack_r = []
m = int(sys.stdin.readline())

for _ in range(m):
    n = sys.stdin.readline().rstrip().split()
    if n[0] == 'L':
        # 커서 왼쪽으로 옮기기 -> stack_l에서 stack_r로 pop
        if stack_l: # 비어있지 않다면
            stack_r.append(stack_l.pop())
    elif n[0] == 'D':
        # 커서 오른쪽으로 옮기기 -> stack_r에서 stack_l로 pop
        if stack_r:
            stack_l.append(stack_r.pop())
    elif n[0] == 'B':
        # 커서 왼쪽 문자 삭제 -> stack_l에서 pop
        if stack_l:
            stack_l.pop()
    elif n[0] == 'P':
        # n[1]을 커서 왼쪽에 추가 -> stack_l에 append
        stack_l.append(n[1])
        
print(''.join(stack_l + list(reversed(stack_r))))

Solution 1과 출력하는 부분만 다르다.

 

출력 방식에 대해서는 아래 포스팅의 출력 부분의 2, 3번 참고!

2023.10.17 - [Algorithm & Data structure/알고리즘 문제 풀이] - [Python] 입출력 : 여러 테스트 케이스 입력, 특정 값이 들어올 때까지 입력, 리스트 요소 한 줄에 하나씩 출력

[Python] 입출력 : 여러 테스트 케이스 입력, 특정 값이 들어올 때까지 입력, 리스트 요소 한 줄에

 

위 - Solution2 제출 결과, 아래  - Solution1 제출 결과

제출 결과, 유의미한 차이인지는 잘 모르겠지만 Solution 2의 성능이 더 우수했다.

 

리스트의 요소들을 문자열 형태로 출력할 때 Unpacking Operator *를 더 자주 사용했는데, join 함수를 사용하는 방식도 손에 익혀야겠다고 다짐하게 되었다.

 

---

접근 방식

1. 문자열에서 폭발 문자열을 없애야 하기 때문에 replace()를 사용해 폭발 문자열을 ''로 치환한다.
2. 이후에 문자열에 폭발 문자열이 남아있다면 (폭발 문자열 없앰으로써 다시 폭발 문자열이 생겼다면) 다시 폭발 문자열을 ''로 치환한다. => 반복문을 사용하자.

❌ Solution 1 - 시간 초과

import sys
string = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()

while bomb in string:
    string = string.replace(bomb, '')

if string:
    print(string)    
else:
    print("FRULA")

in 연산자를 사용하니 문자열 내에 폭발 문자열이 있는지 확인하기가 아주 수월했다.

있다면 True, 없다면 False을 반환하므로 while문으로 문자열 내에 폭발 문자열이 없을 때까지 replace()를 돌릴 수 있다.

 

매우 간단하게 구현할 수 있었고, 예제 입력에 대해서도 올바른 출력이 나왔으나 시간 초과가 발생했다. (시간 제한 2초라 괜찮을 줄 알았는데.....^^..

알고리즘 분류를 보니 스택이라고 적혀있어서 어떻게 스택을 이용해 구현할 수 있을지 생각해 보았다.

 

---

접근 방식

에디터 문제에서는 왼쪽 스택과 오른쪽 스택을 뒀다면, 이 문제에서는 왼쪽 스택만 있고 오른쪽엔 문자열이 있는 상태라고 가정하고 접근했다.

 

1. 문자열의 첫 번째 문자부터 스택에 append 해준다.
2. 다 넣은 후에 폭발 문자열이 있는지 확인하는 건 solution 1과 다를 바 없기 때문에, 다른 방식으로 확인해야 한다.
3. 따라서 넣을 때마다 폭발 문자열이 만들어졌는지 확인하고, 
4. 만들어졌다면 pop 해준다.

✅ Solution 2

import sys
string = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()
stack = []

for i in string:
    stack.append(i)
    if ''.join(stack[-(len(bomb)):]) == bomb:
        for _ in range(len(bomb)):
            stack.pop()

if stack:
    print(''.join(stack))
else:
    print("FRULA")

if ''.join(stack[-(len(bomb)):]) == bomb: 절을 작성하는 데에 시간을 좀 썼다.

일단 스택이고, 리스트 형태로 요소(문자열의 문자)가 하나씩 들어가 있다. 스택은 선입후출이므로 뒤에서부터 폭발 문자열의 길이만큼을 문자열로 변환해 검사하고, 만약 폭발 문자열과 같다면 폭발 문자열 길이만큼의 요소를 하나씩 pop 해주어야 한다.

 

에디터 문제에서 얻은 교훈을 바탕으로 리스트 요소를 문자열로 변환할 때 join을 사용해보았다. (▀̿Ĺ̯▀̿ ̿) V

 

---

 

알고리즘 분류를 보지 않은 상태로는 스택을 떠올리기가 쉽지 않았다.

 

스택은 단순하고 빠른 성능을 위해 사용되는 자료구조이기 때문에, 빠르게 문제를 풀어야 하는데 리스트로 구현할 수 있을 것 같을 때 스택을 사용하면 될 것 같다.

그리고 스택은 구현보단 아이디어를 떠올리는게 어려워서 많은 문제를 접해보면서 다양한 풀이 방식에 대한 연습을 해야겠다.

 

---

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

1406번: 에디터

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

9935번: 문자열 폭발