[자료구조] [BJ1406] 에디터

코드 플러스

🚩 문제 설명

⏱️ 시간 복잡도
▪️ 문자열의 길이가 N으로 주어진다.
▪️ 명령어의 갯수는 M으로 주어진다.
▪️ 명령어의 갯수대로 문자열을 변환해야 하므로 시간 복잡도는 O (M) 이라고 할 수 있다.
▪️ 최악의 경우를 구해보자면 O(50만) 이라고 할 수 있다.
▪️ 이는 5 x 10^5 / 10^8 = 5 / 10^3 이므로 0.005초 라고 볼 수 있다.

◾ 한 줄로 된 간단한 에디터를 구현하는 문제

◾ 마지막에 편집기에 나타나있는 문자열을 출력해야 한다.

◾ 영어 소문자만 편집 가능하다.

◾ 최대 60만 글자 까지 입력 가능.

◾ 커서가 존재할 수 있는 곳

(즉, 길이가 L인 문자열에서 커서의 위치는 L + 1 가지 경우가 있음.)

1. 문장의 맨 앞
2. 문장의 맨 뒤
3. 문장 중간 임의의 곳

◾ 편집기 명령어

• L : 커서를 왼쪽으로 한 칸 옮김
  • 커서가 맨 앞에 있으면 무시
• D : 커서를 오른쪽으로 한 칸 옮김
  • 커서가 맨 뒤에 있으면 무시
• B : 커서 왼쪽에 있는 문자를 삭제
  • 커서가 맨 앞에 있으면 무시
  • 삭제로 인하여 커서는 한 칸 왼쪽으로 이동한 것 처럼 보임. 하지만 커서 오른쪽 문자는 그대로.
• P $ : $라는 문자를 커서 왼쪽에 추가함

◾ 문제의 이해는 다음과 같다.

 

✔️ 예시

◾ 커서의 위치를 | 라고 표시하자.

string	command	return
abcd |
abcd |	P x	abcd | x
abcdx |	L	abcd | x
abcd | x	P y	abcd | yx

 

 

 

---

 

 

 

✅ 입출력

return ➡️ 에디터 편집을 다 마치고 난 후의 문자열을 반환

✔️ 예제 1

abcd
3
P x
L
P y

abcdyx

 

✔️ 예제 2

abc
9
L
L
L
L
L
P x
L
B
P y

yxabc

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

s = input()  # 주어지는 문자열
N = int(input())  # 명령어의 갯수
com = [input() for _ in range(N)] # 입력 명령어
stack = []

# 배열로 변환
for ss in s:
    stack.append(ss)
stack.append('|') # 커서 추가

cur = stack.index('|') # 커서 위치
for c in com:
    splited = c.split() # 명령어 뽑기

    if splited[0] == 'P':
        if cur - 1 < 0:
            cur = 0
        stack.insert(cur, splited[1])
        cur = stack.index("|")

    if splited[0] == 'L':
        prev = cur - 1
        if prev < 0:
            continue
        stack[prev], stack[cur] = stack[cur], stack[prev]
        cur = stack.index("|")

    if splited[0] == 'B':
        prev = cur - 1
        if prev < 0:
            continue
        del stack[prev]
        cur = stack.index("|")

    if splited[0] == 'D':
        next = cur + 1
        if next > len(stack) - 1:
            continue
        stack[next], stack[cur] = stack[cur], stack[next]
        cur = stack.index("|")


stack.remove("|")
print(''.join(stack))

◾ 해당 코드는 시간초과가 걸린다.

◾ 내 생각엔 insert가 문제 인 것 같음.

⏱️ 시간 복잡도
▪️ 해당 코드의 시간 복잡도를 구해보자.
▪️ 일단 명령어를 받는 데에 O(M) 이라고 하고
▪️ 문자열을 배열로 변환하는데 O(N) 이라 하자.
▪️ 명령어 마다의 반복문을 다시 돌기떄문에 O(M)
▪️ O(50만) + O(10만) + O(4x50만) = O(26 x 10^5) = 대략 3 x 10^6으로 잡으면 = 0.3s
▪️ 사실상 반복문을 기준으로 세서 이렇게 나오는 거지 만약 연산 횟수 하나하나당 하면 0.3s 보다 더 나오게 됨.

 

📝 문제 풀이

stackL = list(input())  # 주어지는 문자열
stackR = []
N = int(input())  # 명령어의 갯수


for i in range(N):
    com = input()
    splited = com.split()

    if splited[0] == 'P':
        stackL.append(splited[1])

    elif splited[0] == 'L':
        if len(stackL) != 0:
            stackR.append(stackL.pop())

    elif splited[0] == 'B':
        if len(stackL) != 0:
            stackL.pop()

    else:
        if len(stackR) != 0:
            stackL.append(stackR.pop())

print(''.join(stackL) + ''.join(reversed(stackR)))

💬 Point

➡️  stackL, stackR : 두 개의 스택을 사용한다.
➡️  ''.join() 함수로 stack 배열을 이어준다.

◾ 이 문제는 왜 풀 때마다 틀리지? 😡

◾ 스택 두개를 사용해주면 잘 풀리는 문제이다.

◾ 시간이 0.3초가 되기 때문에 여러 N에 걸쳐서 풀면 안풀린다..

◾ stackL과 stackR 그 사이가 커서라고 보면 된다.

◾ 마지막에 출력할때는 stackR은 reversed() 함수를 사용하여 거꾸로 출력해준다.

 

 

 

 

 

 

 

 

 

 

 

---