DevelopmentAlgorithm

ACMICPC - 에디터(1406)

Algorithm

에디터

처음에 이 문제를 보았을때 가장 문제가 되었던건 문자열 중간에 문자를 추가, 삭제하는 연산이었다.
입력받는 문자열의 최대 길이가 10만이고 명령어가 최대 50만개 들어올 수 있는 상황이라 O(N)이 걸리는 추가/삭제 연산때문에 시간 초과가 뜰 것 같았다.

처음에 짰던 소스는 이랬다.

first.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
text = list(raw_input())
idx = len(text)

N = input()

for i in range(N):
    cmd = raw_input().split()
    if cmd[0] == 'L':
        if idx == 0:
            continue
        idx -= 1
    elif cmd[0] == 'D':
        if idx == len(text):
            continue
        idx += 1
    elif cmd[0] == 'B':
        if idx == 0:
            continue
        text.pop(idx - 1)
        idx -= 1
    elif cmd[0] == 'P':
        text.insert(idx, cmd[1])
        idx += 1

print ''.join(text)

그리고 역시나 예상과 동일하게…

그래서 나온 해결책은 이러했다.
커서를 중심으로 왼쪽과 오른쪽 스택을 구성하는 것이다. push, pop 연산은 O(1)이기 때문에 더 빠르게 할 수 있을것이라 생각했다.
그렇게 명령어별로 왼쪽과 오른쪽 스택에 이루어지는 연산을 정리해볼 수 있었다.

왼쪽 스택 : leftST
오른쪽 스택 : rightST

명령어 연산
L ch = leftST.pop()
rightST.push(ch)
D ch = rightST.pop()
leftST.push(ch)
B leftST.pop()
P $ leftST.push($)

이걸 토대로 소스를 작성해보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
leftST = list(raw_input())
rightST = []

N = input()

for i in range(N):
    cmd = raw_input().split()
    if cmd[0] == 'L':
        if not leftST:
            continue
        ch = leftST.pop()
        rightST.append(ch)
    elif cmd[0] == 'D':
        if not rightST:
            continue
        ch = rightST.pop()
        leftST.append(ch)
    elif cmd[0] == 'B':
        if not leftST:
            continue
        leftST.pop()
    elif cmd[0] == 'P':
        leftST.append(cmd[1])

print leftST, rightST

그런데 stack에서 pop으로 문자열을 하나하나 가져와서 이어붙이려고 했지만 그렇게 되면 leftST에 있는 문자열은 거꾸로 나오게 된다.

ex)

1
2
3
4
5
leftST = ['a', 'b', 'c', 'd']
print leftST.pop() # d
print leftST.pop() # c
print leftST.pop() # b
print leftST.pop() # a

C로 안풀고 python으로 푸는만큼 ''.join이나 [::-1]을 쓰지않고 해결해 보고자 했다.

해결 방법은 간단했다. leftST을 전부 pop해서 rightST에 push한 다음 rightST을 전부 pop하면 올바른 순서로 나오게 된다!

1
2
3
4
5
6
7
8
while leftST:
  ch = leftST.pop()
  rightST.append(ch)

output = ''
while rightST:
  output += rightST.pop()
print output

채점 성공..!!!

그렇게 완성된 최종 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
leftST = list(raw_input())
rightST = []

N = input()

for i in range(N):
    cmd = raw_input().split()
    if cmd[0] == 'L':
        if not leftST:
            continue
        ch = leftST.pop()
        rightST.append(ch)
    elif cmd[0] == 'D':
        if not rightST:
            continue
        ch = rightST.pop()
        leftST.append(ch)
    elif cmd[0] == 'B':
        if not leftST:
            continue
        leftST.pop()
    elif cmd[0] == 'P':
        leftST.append(cmd[1])

while leftST:
  ch = leftST.pop()
  rightST.append(ch)

output = ''
while rightST:
  output += rightST.pop()
print output

이제 슬슬 알고리즘 공부도 계속 하려고 하는데 하루에 한개씩이라도 꾸준하게 할 수 있었으면 좋겠다.

p.s 백준 풀려면 C++로 해야 시간 초과 안뜨려나…

Share